1		% (c) 2019-2023 Lehrstuhl fuer Softwaretechnik und Programmiersprachen,
2		% Heinrich Heine Universitaet Duesseldorf
3		% This software is licenced under EPL 1.0 (http://www.eclipse.org/org/documents/epl-v10.html)
4
5		:- module(cdclt_sat_solver, [b_to_cnf_safe/3,
6		create_solver_state/1,
7		sat/3,
8		sat/4,
9		sat/5,
10		restarts/1,
11		is_backjumping/0,
12		announce_bt_from_smt_solution/0,
13		store_idl_unsat_core/1,
14		log_theory_propagation_sat_stack/4,
15		set_variable_references_in_clauses/3,
16		remove_idl_unsat_core/0,
17		unit_propagate_cnf/4,
18		get_bindings_from_ids/6,
19		portray_cnf/1,
20		cnf_to_smt/2,
21		clear_pending_theory_propagations/0,
22		unfixed_deferred_set_error_occurred/0,
23		severe_error_occurred/0,
24		assignment_timeout_occurred/0,
25		log_det_theory_timeout/1,
26		sat_bindings_to_smt_formula/2]).
27
28		:- meta_predicate asserta_once(0).
29		:- meta_predicate retract_if_exists(0).
30		:- meta_predicate retract_once(0).
31		:- meta_predicate bt_asserta(0).
32		:- meta_predicate bt_retract(0).
33
34		:- use_module(library(lists)).
35		:- use_module(library(sets), [subtract/3]).
36		:- use_module(library(heaps)).
37		:- use_module(library(ordsets)).
38		:- use_module(library(timeout)).
39		:- use_module(library(samsort)).
40		:- use_module(library(plunit)).
41
42		:- use_module(smt_solvers_interface(ast_optimizer_for_smt)).
43		:- use_module(cdclt_solver('cdclt_stats')).
44		:- use_module(cdclt_solver('cdclt_pred_to_sat')).
45		:- use_module(cdclt_solver('cdclt_settings')).
46		:- use_module(cdclt_solver('symmetry_check/sat_symmetry_breaking')).
47		:- use_module(probsrc(b_global_sets), [list_contains_unfixed_deferred_set_id/1]).
48		:- use_module(probsrc(bsyntaxtree),[get_texpr_expr/2,
49		find_typed_identifier_uses/3,
50		safe_create_texpr/4,
51		create_texpr/4,
52		disjunct_predicates/2,
53		conjunct_predicates/2,
54		conjunction_to_list/2]).
55		:- use_module(probsrc(debug)).
56		:- use_module(probsrc(preferences), [temporary_set_preference/3,
57		reset_temporary_preference/2]).
58		:- use_module(probsrc(error_manager), [add_internal_error/2,
59		add_error_fail/3,
60		check_error_occured/2,
61		error_occurred_in_error_scope/0]).
62		:- use_module(probsrc(translate), [translate_bexpression/2]).
63		:- use_module(extrasrc(unsat_cores), [unsat_core_with_fixed_conjuncts/3,
64		unsat_chr_core_list_with_auto_time_limit/5]).
65		:- use_module(probsrc(module_information), [module_info/2]).
66
67		:- use_module(extension('fibonacci_heap/fibonacci_heap')).
68		%:- use_module(probsrc(tools_portability), [exists_source/1]).
69
70		:- module_info(group, cdclt).
71		:- module_info(description,'This module provides the SAT solver for CDCL(T) implementing CDCL with backjumping and further improvements.').
72
73		:- dynamic solver_name/1, backjump_clause/6, backjump_level/1, conflict_stats/3, saved_phase/2, restarts/1,
74		bt_from_smt_solution/0, is_restart/0, exclude_sat_solution_clause/1, total_lbd_sum/1, recent_lbds_dl/2, recent_stack_sizes_dl/2, luby_counter/1,
75		amount_clause_reductions/1, amount_learned_clauses/1, idl_unsat_core/1, pending_theory_prop/2, unfixed_deferred_set_error/0, assignment_count_on_cur_level/1,
76		glue_level/3, glue_clauses/1, allow_partial_model/0, assignment_timeout_occurred/0.
77
78		%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
79		% A sat solver utilising delay declaration to implement watched literals.
80		% Authors: Jacob Howe and Andy King
81		%
82		% Extended for CDCL(T) with first UIP conflict-driven clause learning,
83		% theory propagation, branching heuristics, phase saving for rapid restarts,
84		% learned clause reduction, clause minimization, random restarts, and static SMT symmetry breaking.
85		%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
86
87		% possible improvements:
88		% (- FirstNewCutscheme (cf. https://www.aaai.org/Papers/JAIR/Vol22/JAIR-2210.pdf))
89		% [] improve implying constraint detection (e.g., :cdclt x > y & gt : {x+1} & y > gt)
90		% -> might be overkill at some point
91		% [] clause minimization (cf. Definition 9, "Towards Understanding and Harnessing the Potential of Clause Learning")
92		% [] check out "Advances in Symmetry Breaking for SAT Modulo Theories" by Dinliwal et al. for static SMT symmetry breaking
93
94		%:- if(exists_source(library(mutdict))).
95		%:- use_module(library(mutdict)).
96		%:- else.
97		% mutdict throws a segmentation fault in SICStus 4.8.0, don't use it until the bug is fixed
98		:- use_module(library(avl)).
99		mutdict_empty(Dict) :-
100		get_mutable(Avl, Dict),
101		empty_avl(Avl).
102
103		new_mutdict(Dict) :-
104		empty_avl(Avl),
105		create_mutable(Avl, Dict).
106
107		mutdict_put(Dict, Key, Value) :-
108		get_mutable(Avl, Dict),
109		avl_store(Key, Avl, Value, NewAvl),
110		update_mutable(NewAvl, Dict).
111
112		mutdict_get(Dict, Key, Value) :-
113		get_mutable(Avl, Dict),
114		avl_fetch(Key, Avl, Value).
115
116		mutdict_keys(Dict, Keys) :-
117		get_mutable(Avl, Dict),
118		avl_domain(Avl, Keys).
119
120		mutdict_update(Dict, Key, OldValue, NewValue) :-
121		get_mutable(Avl, Dict),
122		avl_change(Key, Avl, OldValue, NewAvl, NewValue),
123		update_mutable(NewAvl, Dict).
124
125		mutdict_delete(Dict, Key) :-
126		get_mutable(Avl, Dict),
127		avl_delete(Key, Avl, _, NewAvl),
128		update_mutable(NewAvl, Dict).
129
130		mutdict_items(Dict, Items) :-
131		get_mutable(Avl, Dict),
132		avl_to_list(Avl, Items).
133
134		%mutdict_values(Dict, Values) :-
135		% get_mutable(Avl, Dict),
136		% avl_range(Avl, Values).
137		%:- endif.
138
139		pretty_print_clause([], []).
140		pretty_print_clause([_-Pol-Var-Name|T], [Pol-Var-Name|NT]) :-
141		pretty_print_clause(T, NT).
142
143		pretty_print_vars([], []).
144		pretty_print_vars([strip-Var|T], [NVar|NT]) :-
145		!,
146		pretty_print_clause(Var, NVar),
147		pretty_print_vars(T, NT).
148		pretty_print_vars([Var|T], [Var|NT]) :-
149		pretty_print_vars(T, NT).
150
151		debug_format_sat(_, _) :-
152		print_logs(false),
153		!.
154		debug_format_sat(Msg, Vars) :-
155		append(Msg, " (CDCL(T) SAT Solver)~n", NCodes),
156		atom_codes(NMsg, NCodes),
157		pretty_print_vars(Vars, NVars),
158		format(NMsg, NVars), !.
159
160		debug_format_sat(_, _, _) :-
161		print_logs(false),
162		!.
163		debug_format_sat(Msg, Vars, Pred) :-
164		format(Msg, Vars),
165		translate:print_bexpr(Pred), nl, !.
166
167		unfixed_deferred_set_error_occurred :-
168		unfixed_deferred_set_error.
169
170		assignment_count_on_cur_level(0).
171
172		reset_assignment_count_on_level :-
173		retract(assignment_count_on_cur_level(Old)),
174		asserta(assignment_count_on_cur_level(0)),
175		( true
176		; retract(assignment_count_on_cur_level(_)),
177		asserta(assignment_count_on_cur_level(Old)),
178		fail
179		).
180
181		get_next_assignment_count_on_level(NCount) :-
182		retract(assignment_count_on_cur_level(Count)),
183		NCount is Count + 1,
184		asserta(assignment_count_on_cur_level(NCount)),
185		( true
186		; retract(assignment_count_on_cur_level(_)),
187		asserta(assignment_count_on_cur_level(Count)),
188		fail
189		).
190
191		clear_pending_theory_propagations :-
192		retractall_once(pending_theory_prop(_,_)).
193
194		% this is just to replay the same order as is propagated to ProB using coroutines
195		plvar_sort(_-(_-_-_-(_,(DLevel1,ACount1),_,_)), _-(_-_-_-(_,(DLevel2,ACount2),_,_))) :-
196		ground(DLevel1), ground(DLevel2),
197		( DLevel1 < DLevel2
198		-> true
199		; DLevel1 == DLevel2
200		-> ACount1 < ACount2
201		; fail
202		).
203
204		sat_bindings_to_smt_formula(PlVars, SmtFormula) :-
205		mutdict_items(PlVars, PlItems),
206		samsort(plvar_sort, PlItems, SPlItems),
207		sat_bindings_to_smt_formula_aux(SPlItems, b(truth,pred,[]), SmtFormula).
208
209		sat_bindings_to_smt_formula_aux([], Acc, Acc).
210		sat_bindings_to_smt_formula_aux([_-(PrologVar-_-TTheoryConstraint-_)|T], Acc, SmtFormula) :-
211		ground(PrologVar),
212		!,
213		get_smt_formula_for_sat_pol(TTheoryConstraint, PrologVar, TheoryConstraint),
214		safe_create_texpr(conjunct(Acc,TheoryConstraint), pred, [], NAcc),
215		sat_bindings_to_smt_formula_aux(T, NAcc, SmtFormula).
216		sat_bindings_to_smt_formula_aux([_|T], Acc, SmtFormula) :-
217		sat_bindings_to_smt_formula_aux(T, Acc, SmtFormula).
218
219		%% get_bindings_from_ids(+SatVars, -StackBindings, -SatBindings, -SatVarNames, -IdPrologVarTuples, -PrologSatVarTriple).
220		% Given a set of boolean B identifiers. Create a list of bindings containing terms bind/2
221		% and a list of tuples of B identifier and corresponding Prolog variable used for sat solving.
222		% StackBindings contain the bind/2 terms as well as the StackInfo in order to unify Prolog variables in b_to_cnf_safe/3.
223		get_bindings_from_ids(SatVars, StackBindings, SatBindings, SatVarNames, IdPrologVarTuples, PrologSatVarTriple) :-
224		new_mutdict(EmptyDict),
225		get_bindings_from_ids_acc(SatVars, [], [], [], [], EmptyDict, StackBindings, SatBindings, SatVarNames, IdPrologVarTuples, PrologSatVarTriple), !.
226
227		get_bindings_from_ids_acc([], AccStackBindings, AccBindings, AccNames, AccTuples, AccPlVars, AccStackBindings, AccBindings, AccNames, AccTuples, AccPlVars).
228		get_bindings_from_ids_acc([b(identifier(Name),IdType,IdInfo)|T], AccStackBindings, AccBindings, AccNames, AccTuples, AccPlVars, StackBindings, SatBindings, SatVarNames, IdPrologVarTuples, PrologSatVarTriple) :-
229		NewAccBindings = [bind(Name,PrologVar)|AccBindings],
230		% we add Prolog variables for stack infos to each var so that we do not have to maintain a genuine stack
231		StackInfo = (_PropType, _Level, _Pol, _OriginalClause),
232		NewAccStackBindings = [bind(Name,PrologVar)-StackInfo|AccStackBindings],
233		NewAccTuples = [(b(identifier(Name),IdType,IdInfo),PrologVar,StackInfo)|AccTuples],
234		!,
235		( member(smt_formula(SmtFormula), IdInfo)
236		-> mutdict_put(AccPlVars, Name, PrologVar-Name-SmtFormula-StackInfo)
237		; % plain SAT variable which is not reified with a theory solver, e.g., introduced by CNF optimization rewriting
238		OptEq = b(equal(b(identifier(Name),boolean,[]),b(boolean_true,boolean,[])),pred,[]),
239		mutdict_put(AccPlVars, Name, PrologVar-Name-OptEq-StackInfo)
240		),
241		get_bindings_from_ids_acc(T, NewAccStackBindings, NewAccBindings, [Name|AccNames], NewAccTuples, AccPlVars, StackBindings, SatBindings, SatVarNames, IdPrologVarTuples, PrologSatVarTriple).
242		get_bindings_from_ids_acc([_|T], AccStackBindings, AccBindings, AccNames, AccTuples, AccPlVars, StackBindings, SatBindings, SatVarNames, IdPrologVarTuples, PrologSatVarTriple) :-
243		get_bindings_from_ids_acc(T, AccStackBindings, AccBindings, AccNames, AccTuples, AccPlVars, StackBindings, SatBindings, SatVarNames, IdPrologVarTuples, PrologSatVarTriple).
244
245		%% sat(+SolverName, +SolverEnv, +Clauses).
246		% SolverEnv is a list [sat_vars:_, sat_varnames:_, sat_bindings:_, t2b_env:_, pl_vars:_].
247		% sat_vars are boolean b/3 identifier ASTs for corresponding SAT variables in Clauses.
248		% sat_bindings is a list of terms bind/2 as used by the ProB constraint solver.
249		% t2b_env is the environment mapping SAT variable names and theory formulae used to
250		% translate B predicates to SAT.
251		% pl_vars is a dict of tuples PrologVar-SatVarName-SmtFormula-StackInfo.
252		sat(SolverName, SolverEnv, Clauses) :-
253		debug_format_sat("Start SAT solving with solver ~w ", [SolverName]),
254		init_dynamic_solver_state(SolverName),
255		create_solver_state(StateMutable),
256		get_from_solver_env(SolverEnv, binary_clause_vars, VarsFromBinaryClauses),
257		init_decision_heuristic(StateMutable, VarsFromBinaryClauses, Clauses),
258		sat_stateful_pre(SolverEnv, StateMutable, Clauses).
259
260		%% sat(+SolverName, +SolverEnv, +StateMutable, +Clauses).
261		sat(SolverName, SolverEnv, StateMutable, Clauses) :-
262		sat(SolverName, SolverEnv, StateMutable, Clauses, []).
263
264		%% sat(+SolverName, +SolverEnv, +StateMutable, +Clauses, +Options).
265		% Options:
266		% allow_partial_model: only for SMT solving: possibly does not assign all SAT variables,
267		% but the reification with ProB ensures that all coroutines are triggered
268		sat(SolverName, SolverEnv, StateMutable, Clauses, Options) :-
269		debug_format_sat("Start SAT solving with solver ~w ", [SolverName]),
270		init_dynamic_solver_state(SolverName),
271		( memberchk(allow_partial_model, Options)
272		-> asserta(allow_partial_model)
273		; true
274		),
275		get_from_solver_env(SolverEnv, binary_clause_vars, VarsFromBinaryClauses),
276		init_decision_heuristic(StateMutable, VarsFromBinaryClauses, Clauses),
277		sat_stateful_pre(SolverEnv, StateMutable, Clauses).
278
279		% Wrapper for sat_stateful_restart_cp/3 to enable backjumping to level 0 several times.
280		sat_stateful_pre(SolverEnv, StateMutable, Clauses) :-
281		\+ severe_error_occurred,
282		sat_stateful_restart_cp(SolverEnv, StateMutable, Clauses).
283
284		sat_stateful_restart_cp(SolverEnv, StateMutable, Clauses) :-
285		( sat_stateful(SolverEnv, StateMutable, Clauses)
286		; % we either learned a unit-clause from conflict analysis or randomly restart
287		% in both cases, we learn all asserted backjump clauses
288		retract(backjump_level(0)),
289		( retract(is_restart)
290		-> debug_format_sat("backjump to level 0 random restart", []),
291		backjump_clause(LearnFromLevel,_,_,_,_,_)
292		; debug_format_sat("backjump to level 0", []),
293		LearnFromLevel = 0
294		),
295		learn_backjump_clause(LearnFromLevel, SolverEnv, StateMutable),
296		sat_stateful_pre(SolverEnv, StateMutable, Clauses)
297		).
298
299		%% sat_stateful(+Clauses, +StateMutable, +Clauses).
300		% CDCL with first UIP conflict-driven clause learning, two-watched literals, EVSIDS branching heuristic,
301		% random glucose restarts, and phase saving for rapid restarts.
302		% See create_solver_state/1 for variable StateMutable.
303		sat_stateful(SolverEnv, StateMutable, Clauses) :-
304		problem_setup(SolverEnv, StateMutable, Clauses),
305		%static_sat_symmetry_breaking(Clauses, SolverEnv, CurLevelMut, NewSolverEnv),
306		elim_vars(SolverEnv, StateMutable).
307
308		%% elim_vars(+SolverEnv, +StateMutable).
309		elim_vars(SolverEnv, StateMutable) :-
310		\+ severe_error_occurred,
311		get_full_state(StateMutable, cur_level, CurLevel),
312		NextLevel is CurLevel + 1,
313		reset_assignment_count_on_level,
314		( % solution found
315		fibonacci_heap:is_empty
316		-> true
317		; elim_vars_from_asserted_heuristic_rapid_restart(SolverEnv, StateMutable, NextLevel)
318		).
319
320		learn_backjump_clause(CurLevel, SolverEnv, StateMutable) :-
321		retract(backjump_clause(BjLevel, BjClause, _, BjSatVars, UsedVars, AC)),
322		( CurLevel == BjLevel
323		-> true
324		; add_error_fail(learn_backjump_clause, 'Inconsistent backjump level: ', [BjLevel,CurLevel])
325		),
326		get_from_solver_env(SolverEnv, pl_vars, PlVars),
327		set_variable_references_in_clause(PlVars, BjClause, BjClauseRef),
328		clause_setup(SolverEnv, StateMutable, BjClauseRef),
329		update_heuristic_scores_for_vars(BjSatVars, AC),
330		( bump_scores_for_bj_clause_only(true)
331		; % additionally bump scores for all variables used during conflict analysis
332		bump_scores_for_bj_clause_only(false),
333		update_heuristic_scores_for_vars(UsedVars, AC)
334		), !.
335
336		possibly_backjump(_, _, _).
337		possibly_backjump(SolverEnv, StateMutable, NextLevel) :-
338		% backjumping to a level other than 0; skip for restart since we then backjump to level 0
339		\+ is_restart,
340		backjump_level(C),
341		debug_format_sat("Current level is ~w and bj level is ~w", [NextLevel,C]),
342		C == NextLevel,
343		retract(backjump_level(C)),
344		debug_format_sat("~nbackjump branch prop level ~w", [NextLevel]),
345		learn_backjump_clause(C, SolverEnv, StateMutable),
346		possibly_bump_glue_variable_scores(NextLevel),
347		possibly_backjump(SolverEnv, StateMutable, NextLevel).
348
349		possibly_bump_glue_variable_scores(CurLevel) :-
350		( ( glue_bumping(true),
351		glue_clauses(GC),
352		GC \== 0
353		)
354		-> bump_glue_variable_scores(GC, CurLevel)
355		; true
356		).
357
358		bump_glue_variable_scores(GC, CurLevel) :-
359		( bt_retract(glue_level(GlueVar,GlueLevel,AlreadyBumped))
360		-> ( ( \+ AlreadyBumped,
361		GlueLevel > CurLevel
362		)
363		-> fibonacci_heap:get_priority_of(GlueVar, Score),
364		bump_glue_variable_score(Score, GlueVar, GlueLevel, GC),
365		bump_glue_variable_scores(GC, CurLevel),
366		bt_asserta(glue_level(GlueVar,GlueLevel,true))
367		; bump_glue_variable_scores(GC, CurLevel),
368		bt_asserta(glue_level(GlueVar,GlueLevel,AlreadyBumped))
369		)
370		; true
371		).
372
373		bump_glue_variable_score(Score, SatVarName, GlueLevel, GC) :-
374		GlueBump is Score * (GlueLevel/GC),
375		NScore is Score + GlueBump,
376		fibonacci_heap:update_bt(SatVarName, NScore).
377
378		%% elim_vars_from_asserted_heuristic_rapid_restart(+SolverEnv, +StateMutable, +NextLevel).
379		elim_vars_from_asserted_heuristic_rapid_restart(SolverEnv, StateMutable, NextLevel) :-
380		\+ backjump_level(_),
381		\+ idl_unsat_core(_),
382		get_sat_var_with_max_heuristic(SatVarName, MaxScore),
383		get_from_solver_env(SolverEnv, pl_vars, PlVars),
384		mutdict_get(PlVars, SatVarName, Var-SatVarName-_-StackInfo), % we need the variable's references
385		debug_format_sat("Max heuristic value with score ~w is ~w", [MaxScore,SatVarName]),
386		possibly_backjump(SolverEnv, StateMutable, NextLevel),
387		( saved_phase(SatVarName, SavedPol)
388		-> % restore phase/polarity from cache for rapid restart
389		SelectedPol = SavedPol,
390		retract(saved_phase(SatVarName, _)), % don't undo when backtracking
391		debug_format_sat("Restore phase of ~w", [SatVarName])
392		; % uninformed phase/polarity selection: start with truth
393		SelectedPol = pred_true
394		),
395		elim_var_for_phase(SatVarName, StackInfo, SelectedPol, Var, SolverEnv, StateMutable, NextLevel).
396
397		%% elim_var_for_phase(+SatVarName, +StackInfo, +SavedPol, +Var, +SolverEnv, +StateMutable, +NextLevel).
398		elim_var_for_phase(SatVarName, StackInfo, SavedPol, Var, SolverEnv, StateMutable, NextLevel) :-
399		( ground(Var)
400		-> add_error_fail(elim_var_for_phase, 'Decision variable is already ground: probably an error in the decision heuristic.', [SatVarName])
401		; true
402		),
403		update_full_state(StateMutable, cur_level, NextLevel),
404		get_next_assignment_count_on_level(ACount),
405		( StackInfo = (branch,(NextLevel,ACount),SavedPol,_OriginalClause),
406		bt_log_sat_stack(StateMutable, SatVarName, SavedPol),
407		debug_format_sat("Decide variable ~w with polarity ~w on level ~w", [SatVarName,SavedPol,NextLevel]),
408		log_boolean_decision,
409		Var = SavedPol
410		; \+ backjump_level(_),
411		\+ severe_error_occurred,
412		negate_polarity(SavedPol, NegSavedPol),
413		StackInfo = (branch,(NextLevel,ACount),NegSavedPol,_OriginalClause),
414		bt_log_sat_stack(StateMutable, SatVarName, NegSavedPol),
415		debug_format_sat("Decide variable ~w with polarity ~w on level ~w", [SatVarName,NegSavedPol,NextLevel]),
416		log_boolean_decision,
417		Var = NegSavedPol
418		),
419		elim_vars(SolverEnv, StateMutable).
420
421		%% checkout_sat_variable(+SatVarName, +OriginalClause).
422		% Remove a SAT variable's information if it has been propagated.
423		checkout_sat_variable(SatVarName, OriginalClause) :-
424		delete_from_heuristic(SatVarName),
425		retract_if_exists(saved_phase(SatVarName, _)),
426		( allow_partial_model
427		-> worsen_scores_for_vars_in_clause(OriginalClause)
428		; true
429		).
430
431		worsen_scores_for_vars_in_clause([]).
432		worsen_scores_for_vars_in_clause([_-_-_-SatVarName|T]) :-
433		( fibonacci_heap:get_priority_of_silent_fail(SatVarName, Score)
434		-> ( Score > 1,
435		fibonacci_heap:dec_priority_of_bt(SatVarName, 1)
436		; Score =< 1,
437		fibonacci_heap:delete_elm_bt(SatVarName)
438		),
439		worsen_scores_for_vars_in_clause(T)
440		; worsen_scores_for_vars_in_clause(T)
441		).
442
443		problem_setup(_, _, []).
444		problem_setup(SolverEnv, StateMutable, [Clause|Clauses]) :-
445		clause_setup(SolverEnv, StateMutable, Clause),
446		problem_setup(SolverEnv, StateMutable, Clauses).
447
448		clause_setup(SolverEnv, StateMutable, Clause) :-
449		Clause = [StackInfo-Pol-Var-SatVarName|Triples],
450		set_watch(SolverEnv, StateMutable, Clause, Triples, Var, Pol, SatVarName, StackInfo).
451
452		set_polarity_of_var_explicitly(_, _, [], []).
453		set_polarity_of_var_explicitly(SatVarName, Pol, [CPol-CVar-CName|T], ConflictClause) :-
454		var(CVar),
455		SatVarName == CName,
456		!,
457		ConflictClause = [CPol-Pol-CName|T].
458		set_polarity_of_var_explicitly(SatVarName, Pol, [Triple|T], [Triple|NT]) :-
459		set_polarity_of_var_explicitly(SatVarName, Pol, T, NT).
460
461		set_watch(_, _, OriginalClause, [], Var, Pol, SatVarName, _) :-
462		Var == Pol,
463		checkout_sat_variable(SatVarName, OriginalClause).
464		set_watch(SolverEnv, StateMutable, OriginalClause, [], Var, Pol, _, _) :-
465		ground(Var),
466		Var \== Pol,
467		\+ severe_error_occurred,
468		\+ backjump_level(_),
469		debug_format_sat("sat conflict", []),
470		clause_learning(true),
471		possibly_bt_from_smt_solution(SolverEnv,StateMutable, _, _),
472		get_full_state(StateMutable, current_stack_size, StackSize),
473		get_full_state(StateMutable, cur_level, CurLevel),
474		assignment_count_on_cur_level(ACount),
475		ACount \== 1, % at least one unit-propagation for CDCL, otherwise just backtrack to the last decision
476		compute_and_assert_backjump_clause(SolverEnv, StateMutable, StackSize, CurLevel, OriginalClause),
477		fail.
478		set_watch(SolverEnv, StateMutable, OriginalClause, [], Var, Pol, SatVarName, StackInfo) :-
479		var(Var),
480		\+ severe_error_occurred,
481		\+ backjump_level(_),
482		get_full_state(StateMutable, cur_level, CurLevel),
483		debug_format_sat("unit propagation of ~w with polarity ~w on level ~w due to clause ~w", [SatVarName,Pol,CurLevel,strip-OriginalClause]),
484		%translate:print_bexpr(TheoryFormula),nl,
485		get_next_assignment_count_on_level(ACount),
486		StackInfo = (unit,(CurLevel,ACount),Pol,OriginalClause),
487		bt_log_sat_stack(StateMutable, SatVarName, Pol),
488		log_unit_propagation,
489		( checkout_sat_variable(SatVarName, OriginalClause),
490		Var = Pol,
491		( true
492		; % remove idl unsat core from higher decision level when backtracking
493		remove_idl_unsat_core,
494		fail
495		)
496		; % theory conflict: if Var = Pol triggered a SAT conflict instead,
497		% a backjump clause has been computed and backjump_level/1 is asserted
498		clause_learning(true),
499		\+ severe_error_occurred,
500		\+ backjump_level(_), % skip when backjumping
501		get_last_decision_level(StateMutable, LastDLevel), % skip if no decision so far
502		LastDLevel > 0, % just backtrack if last decision level is 1 or 0
503		possibly_bt_from_smt_solution(SolverEnv,StateMutable, SatVarName, Pol),
504		( learn_idl_core(StateMutable, SolverEnv, SatVarName, Pol)
505		-> true
506		; debug_format_sat("theory conflict on level ~w", [CurLevel]),
507		get_conflict_clause_for_theory_conflict(SolverEnv, SatVarName, Pol, SolverEnv, TConflictClause),
508		% explicitly set the polarity which failed to be assigned above in line 414 for conflict analysis (possibly part of the unsat core)
509		set_polarity_of_var_explicitly(SatVarName, Pol, TConflictClause, ConflictClause),
510		( ConflictClause = [SStackInfo-CPol-SingletonVar-SingletonName]
511		-> % singleton theory conflict: backjump to level 0
512		debug_format_sat("backjump to level 0 after finding singleton theory conflict for SAT variable ~w", [SingletonName]),
513		( ground(SingletonVar)
514		-> negate_polarity(SingletonVar, NSingletonPol)
515		; % static WD PO theory contradiction
516		debug_format_sat("Force static theory conflict of WD condition to be false for ~w.", [SingletonName]),
517		NSingletonPol = CPol
518		),
519		BjClause = [SStackInfo-NSingletonPol-SingletonVar-SingletonName],
520		debug_format_sat("learn unit clause ~w", [strip-BjClause]),
521		BjLevel = 0,
522		compute_lbd_score(BjClause, LbdScore),
523		count_found_conflict(NewTotal, _, _),
524		asserta(backjump_clause(BjLevel, BjClause, LbdScore, [SingletonName], [], NewTotal)),
525		asserta(backjump_level(BjLevel))
526		; get_maximum_decision_level(ConflictClause, ConflictLevel),
527		% it can be the case that ProB first recognizes unsatisfiable after grounding waitflags; the last decision level is then not necessarily the conflict level
528		debug_format_sat("theory conflict on level ~w after unsat core computation", [ConflictLevel]),
529		get_full_state(StateMutable, current_stack_size, StackSize),
530		compute_and_assert_backjump_clause_get_level(SolverEnv, StateMutable, StackSize, ConflictLevel, ConflictClause, _BjLevel)
531		)
532		),
533		fail
534		).
535		set_watch(SolverEnv, StateMutable, OriginalClause, [StackInfo2-Pol2-Var2-Name2|Triples], Var1, Pol1, Name1, StackInfo1):-
536		\+ backjump_level(_),
537		watch(SolverEnv, StateMutable, OriginalClause, StackInfo1, Var1, Pol1, Name1, StackInfo2, Var2, Pol2, Name2, Triples).
538
539		:- block watch(?, ?, ?, ?, -, ?, ?, ?, -, ?, ?, ?).
540		watch(SolverEnv, StateMutable, OriginalClause, StackInfo1, Var1, Pol1, Name1, StackInfo2, Var2, Pol2, Name2, Triples) :-
541		( nonvar(Var1)
542		-> update_watch(SolverEnv, StateMutable, OriginalClause, StackInfo1, Var1, Pol1, Name1, StackInfo2, Var2, Pol2, Name2, Triples)
543		; update_watch(SolverEnv, StateMutable, OriginalClause, StackInfo2, Var2, Pol2, Name2, StackInfo1, Var1, Pol1, Name1, Triples)
544		).
545
546		update_watch(SolverEnv, StateMutable, OriginalClause, _, Var1, Pol1, Name1, StackInfo2, Var2, Pol2, Name2, Triples) :-
547		( Var1 == Pol1
548		-> checkout_sat_variable(Name1, OriginalClause)
549		; set_watch(SolverEnv, StateMutable, OriginalClause, Triples, Var2, Pol2, Name2, StackInfo2)
550		).
551
552		retract_once(Assertion) :-
553		retract(Assertion),
554		!.
555
556		severe_error_occurred :-
557		error_occurred_in_error_scope,
558		check_error_occured(ErrorName, _),
559		ErrorName \= warning(_),
560		ErrorName \== clpfd_overflow,
561		ErrorName \== smt_symmetry_breaking,
562		ErrorName \== well_definedness_error,
563		ErrorName \== smt_solvers_interface,
564		ErrorName \== internal_error(smt_solvers_interface).
565
566		%% is_backjumping.
567		is_backjumping :-
568		backjump_level(_).
569
570		assert_update_pending_theory_propagation(SatVarName, Pol) :-
571		retract(pending_theory_prop(SatVarName,_)),
572		!,
573		asserta(pending_theory_prop(SatVarName,Pol)).
574		assert_update_pending_theory_propagation(SatVarName, Pol) :-
575		asserta(pending_theory_prop(SatVarName,Pol)).
576
577		% We use a time limit in b_interpreter:b_convert_bool_timeout/7 which is observed here.
578		% It can be the case that ProB/CLP(FD) exceeds the predefined global time limit
579		% when assigning a SAT variable in the deterministic propagation phase (b_convert_bool).
580		% Simply setting a time limit on the SAT variable's unification in the SAT solver is not possible
581		% since CDCL etc. would also be affected by this time limit due to coroutines.
582		:- block log_det_theory_timeout(-).
583		log_det_theory_timeout(TORes) :-
584		( TORes == time_out
585		-> asserta(assignment_timeout_occurred)
586		; true
587		).
588
589		%% log_theory_propagation_sat_stack(+StateMutable, +SatVarName, +SatPrologVar, +StackInfo).
590		log_theory_propagation_sat_stack(StateMutable, SatVarName, SatPrologVar, StackInfo) :-
591		get_full_state(StateMutable, cur_level, CurLevel),
592		log_theory_propagation,
593		!,
594		debug_format_sat("Theory propagation of ~w with polarity ~w", [SatVarName,SatPrologVar]),
595		( SatPrologVar == pred_true -> Pol = pred_true; Pol = pred_false),
596		assert_update_pending_theory_propagation(SatVarName, Pol),
597		% explanation (OriginalClause) is computed lazily for conflict analysis if necessary, see explain_theory_propagation/5
598		get_next_assignment_count_on_level(ACount),
599		StackInfo = (theory,(CurLevel,ACount),Pol,_),
600		bt_log_sat_stack(StateMutable, SatVarName, Pol).
601
602		%% learn_idl_core(+StateMutable, +SolverEnv, +LastSatVarName, +FailedPol).
603		learn_idl_core(StateMutable, SolverEnv, LastSatVarName, FailedPol) :-
604		retract(idl_unsat_core(Core)),
605		remove_idl_unsat_core,
606		!,
607		get_from_solver_env(SolverEnv, pl_vars, PlVars),
608		get_conflict_clause_from_unsat_core(Core, SolverEnv, TConflictClause),
609		% explicitly assign the polarity which was undone due to the conflict
610		set_polarity_of_var_explicitly(LastSatVarName, FailedPol, TConflictClause, TTConflictClause),
611		set_variable_references_in_clause(PlVars, TTConflictClause, ConflictClause),
612		get_full_state(StateMutable, current_stack_size, StackSize),
613		get_full_state(StateMutable, cur_level, CurLevel),
614		compute_and_assert_backjump_clause(SolverEnv, StateMutable, StackSize, CurLevel, ConflictClause).
615
616		save_phase(SatVarName, Pol) :-
617		(retract(saved_phase(SatVarName, _)), !; true),
618		asserta(saved_phase(SatVarName, Pol)).
619
620		% Log variable assignments.
621		% Effect is undone when backtracking. Cache phase when backtracking and unassigning a variable.
622		bt_log_sat_stack(StateMutable, SatVarName, Pol) :-
623		increase_stack_size(StateMutable),
624		( true
625		; save_phase(SatVarName, Pol),
626		fail
627		).
628
629		increase_stack_size(StateMutable) :-
630		get_full_state(StateMutable, current_stack_size, Old),
631		New is Old + 1, !,
632		update_full_state(StateMutable, current_stack_size, New).
633
634		%% possibly_bt_from_smt_solution(+SolverEnv,+StateMutable, +SatVarName, +Pol).
635		% Backtracking from an SMT solution which should not be handled as a theory conflict.
636		possibly_bt_from_smt_solution(SolverEnv,StateMutable, SatVarName, Pol) :-
637		retract(bt_from_smt_solution),
638		!,
639		( ground(SatVarName)
640		-> get_complete_theory_lemma_fixed_binding(SolverEnv, SatVarName, Pol, TheoryLemmaClause)
641		; get_complete_theory_lemma(SolverEnv, TheoryLemmaClause)
642		),
643		% backjump to the last decision level without computing a conflict clause
644		% but excluding the last SAT solution when backtracking after finding an SMT solution
645		get_last_decision_level(StateMutable, Level),
646		asserta(exclude_sat_solution_clause(TheoryLemmaClause)),
647		asserta(backjump_level(Level)),
648		fail.
649		possibly_bt_from_smt_solution(_,_, _, _).
650
651		% Just wrap with negation but prevent double negation.
652		negate_smt_formula(b(negation(Smt),pred,_), NegSmt) :-
653		!,
654		NegSmt = Smt.
655		negate_smt_formula(Smt, b(negation(Smt),pred,[])).
656
657		% iterate over all Prolog variables to find the propagated literals: usually a stack is used but we store stack infos besides each
658		% variable in the clauses; explanation of theory propagations is rare and maintaining a genuine stack is more expensive
659		get_propagated_sat_vars([], _, []).
660		get_propagated_sat_vars([SatVarName-(_-_-_-(_,(Level,_ACount),Pol,_))|T], TheoryPropLevel, SatVarNameTuples) :-
661		ground(Level),
662		Level < TheoryPropLevel,
663		!,
664		SatVarNameTuples = [(SatVarName-Pol)|NT],
665		get_propagated_sat_vars(T, TheoryPropLevel, NT).
666		get_propagated_sat_vars([_|T], TheoryPropLevel, NT) :-
667		get_propagated_sat_vars(T, TheoryPropLevel, NT).
668
669		%% explain_theory_propagation(+SolverEnv, +TheoryPropSatVar, +TheoryPropLevel, +TheoryPropPol, -ExplainingClause).
670		explain_theory_propagation(SolverEnv, TheoryPropSatVar, _, _, ExplainingClause) :-
671		minimize_theory_explanations(false),
672		!,
673		debug_format_sat("Use complete lemma for theory explanation of ~w", [TheoryPropSatVar]),
674		get_from_solver_env(SolverEnv, sat_bindings, SatBindings),
675		get_clause_from_ground_bindings(SatBindings, _, _, [], TExplainingClause),
676		get_from_solver_env(SolverEnv, pl_vars, PlVars),
677		set_variable_references_in_clause(PlVars, TExplainingClause, ExplainingClause),
678		debug_format_sat("finished explanation.", []).
679		explain_theory_propagation(SolverEnv, TheoryPropSatVar, TheoryPropLevel, TheoryPropPol, ExplainingClause) :-
680		debug_format_sat("Explain theory propagation of ~w", [TheoryPropSatVar]),
681		get_from_solver_env(SolverEnv, pl_vars, PlVars),
682		mutdict_items(PlVars, PlVarsList),
683		get_propagated_sat_vars(PlVarsList, TheoryPropLevel, SatVarNameTuples),
684		get_from_solver_env(SolverEnv, sat_vars, SatVars),
685		get_smt_formula_from_vars_for_sat_pol(SatVars, TheoryPropSatVar, TheoryPropPol, SmtFormula),
686		negate_smt_formula(SmtFormula, NegSmt),
687		debug_format_sat("Compute unsat core for explanation: ", [], NegSmt),
688		get_explanation_candidate_formula(SatVars, SatVarNameTuples, CandidateFormula),
689		( SatVarNameTuples = [_]
690		-> safe_create_texpr(conjunct(CandidateFormula,NegSmt), pred, [], UnsatCore)
691		; temporary_set_preference(time_out, 25, Change1),
692		temporary_set_preference(unsat_core_algorithm, linear, Change2),
693		call_cleanup(unsat_core_with_fixed_conjuncts(CandidateFormula, NegSmt, TTUnsatCore),
694		(reset_temporary_preference(unsat_core_algorithm, Change2),
695		reset_temporary_preference(time_out, Change1))),
696		safe_create_texpr(conjunct(TTUnsatCore,NegSmt), pred, [], TUnsatCore),
697		( remove_wd_pos_introduced_for_cdclt_keep_toplevel(TUnsatCore, UnsatCore)
698		-> true
699		; add_error_fail(remove_wd_pos_introduced_for_cdclt_keep_toplevel, 'Removing WD POs for CDCL(T) failed for explaining theory propagation.', [unsat_core_with_wd:TUnsatCore])
700		)
701		),
702		get_from_solver_env(SolverEnv, t2b_env, T2BEnv),
703		debug_format_sat("Computed unsat core for explanation: ", [], UnsatCore),
704		(
705		(
706		predicate_to_sat(only_reuse, [], SatVars, T2BEnv, UnsatCore, _NewEnv, _, UnsatCoreSat, _NewSatVars),
707		sat_conj_negate_to_clause(UnsatCoreSat, TExplainingClause)
708		)
709		-> true
710		; add_error_fail(sat_conj_negate_to_clause, 'Explaining theory propagation failed: Explanation cannot be transformed to SAT.', [unsat_core:UnsatCore])
711		),
712		debug_format_sat("finished explanation.", []),
713		set_variable_references_in_clause(PlVars, TExplainingClause, TTExplainingClause),
714		sort(TTExplainingClause, ExplainingClause).
715
716		get_explanation_candidate_formula(SatVars, [SatVarName-Pol|T], CandidateFormula) :-
717		get_smt_formula_from_vars_for_sat_pol(SatVars, SatVarName, Pol, SmtFormula),
718		!,
719		get_explanation_candidate_formula_acc(SatVars, T, SmtFormula, CandidateFormula).
720		get_explanation_candidate_formula(SatVars, [_|T], CandidateFormula) :-
721		% can be artificial SAT variable introduced by cnf rewriting
722		get_explanation_candidate_formula(SatVars, T, CandidateFormula).
723
724		get_explanation_candidate_formula_acc(_, [], Acc, Acc).
725		get_explanation_candidate_formula_acc(SatVars, [SatVarName-Pol|T], Acc, CandidateFormula) :-
726		get_smt_formula_from_vars_for_sat_pol(SatVars, SatVarName, Pol, SmtFormula),
727		!,
728		safe_create_texpr(conjunct(SmtFormula,Acc), pred, [], NAcc),
729		get_explanation_candidate_formula_acc(SatVars, T, NAcc, CandidateFormula).
730		get_explanation_candidate_formula_acc(SatVars, [_|T], Acc, CandidateFormula) :-
731		get_explanation_candidate_formula_acc(SatVars, T, Acc, CandidateFormula).
732
733		get_smt_formula_from_vars_for_sat_pol(SatVars, SatVarName, Pol, SmtFormula) :-
734		memberchk(b(identifier(SatVarName),_,Info), SatVars),
735		member(smt_formula(TSmtFormula), Info),
736		get_smt_formula_for_sat_pol(TSmtFormula, Pol, SmtFormula).
737
738		get_smt_formula_for_sat_pol(TSmtFormula, Pol, SmtFormula) :-
739		( Pol == pred_true
740		-> SmtFormula = TSmtFormula
741		; TSmtFormula = b(negation(SmtFormula),pred,[])
742		-> true
743		; TSmtFormula = b(_,_,Info),
744		SmtFormula = b(negation(TSmtFormula),pred,Info)
745		).
746
747		%% get_sat_var_with_max_heuristic(-SatVarName, -MaxScore).
748		get_sat_var_with_max_heuristic(SatVarName, MaxScore) :-
749		%\+ fibonacci_heap:is_empty,
750		( print_logs(true)
751		-> fibonacci_heap:get_max_priority(MaxScore)
752		; MaxScore = -1
753		),
754		fibonacci_heap:get_and_remove_max_value_bt(SatVarName).
755
756		retract_if_exists(Assertion) :-
757		( cdclt_sat_solver:Assertion
758		-> retract(cdclt_sat_solver:Assertion)
759		; true
760		).
761
762		% Periodically decay heuristic scores for VSIDS heuristic.
763		% Not undone when backtracking.
764		possibly_decay_heuristic_values :-
765		decision_heuristic(vsids),
766		conflict_stats(total(AC), _, _),
767		AC \== 0,
768		vsids_decay_frequency(I),
769		C is AC mod I,
770		C == 0,
771		debug_format_sat("~nDecay heuristic scores", []),
772		!,
773		vsids_decay_value(Val),
774		decay_heuristic_values(Val).
775		possibly_decay_heuristic_values.
776
777		%% decay_heuristic_values(+DecayValue).
778		% Not undone when backtracking.
779		decay_heuristic_values(DecayValue) :-
780		Decay is (1/DecayValue),
781		fibonacci_heap:mult_priority_of_all(Decay).
782
783		%% init_decision_heuristic(+StateMutable, +VarsFromBinaryClauses, +Clauses).
784		% Each variable is initially assigned the number of its occurrences in all clauses as its score.
785		% Variable scores are not split for polarities.
786		init_decision_heuristic(StateMutable, VarsFromBinaryClauses, Clauses) :-
787		count_var_occurrences_in_clauses(Clauses, VarScoreTuples),
788		binary_boost_factor(BoostFactor),
789		add_heuristic_tuples(StateMutable, BoostFactor, VarsFromBinaryClauses, VarScoreTuples).
790
791		add_heuristic_tuples(_, _, _, []).
792		add_heuristic_tuples(StateMutable, BoostFactor, VarsFromBinaryClauses, [SatVarName-Score|T]) :-
793		( select(SatVarName, VarsFromBinaryClauses, TVarsFromBinaryClauses)
794		-> NScore is Score * BoostFactor
795		; NScore = Score,
796		TVarsFromBinaryClauses = VarsFromBinaryClauses
797		),
798		fibonacci_heap:push(NScore, SatVarName),
799		add_heuristic_tuples(StateMutable, BoostFactor, TVarsFromBinaryClauses, T).
800
801		count_var_occurrences_in_clauses(Clauses, DictItems) :-
802		new_mutdict(Dict),
803		count_var_occurrences_dict(Dict, Clauses), !,
804		mutdict_items(Dict, DictItems), !.
805
806		count_var_occurrences_dict(_, []).
807		count_var_occurrences_dict(Dict, [Clause|T]) :-
808		count_var_occurrences_from_clause_dict(Dict, Clause),
809		count_var_occurrences_dict(Dict, T).
810
811		count_var_occurrences_from_clause_dict(_, []).
812		count_var_occurrences_from_clause_dict(Dict, [_-_-Pol-SatVarName|T]) :-
813		var(Pol), % skip variables that are already propagated by deterministic unit propagation
814		!,
815		( mutdict_get(Dict, SatVarName, Score)
816		-> Score1 is Score + 1,
817		mutdict_update(Dict, SatVarName, _, Score1)
818		; mutdict_put(Dict, SatVarName, 1)
819		),
820		count_var_occurrences_from_clause_dict(Dict, T).
821		count_var_occurrences_from_clause_dict(Dict, [_|T]) :-
822		count_var_occurrences_from_clause_dict(Dict, T).
823
824		update_heuristic_scores_for_vars(UsedVars, AC) :-
825		decision_heuristic(Type),
826		update_heuristic_scores(AC, Type, UsedVars).
827
828		%% update_heuristic_scores(+AmountOfConflitsAtLevel, +Type, +SatVarNames).
829		% Type is either vsids, evsids, vmtf or acids.
830		% SatVarNames are the variable names occurring in learned clauses.
831		update_heuristic_scores(_, _, []).
832		update_heuristic_scores(TotalConflicts, Type, [SatVarName|T]) :-
833		( fibonacci_heap:get_priority_of_silent_fail(SatVarName, OldScore)
834		-> bump_heuristic_score_for_type(Type, TotalConflicts, OldScore, NewScore),
835		fibonacci_heap:update(SatVarName, NewScore),
836		update_heuristic_scores(TotalConflicts, Type, T)
837		; % SAT variable has already been propagated.
838		% For instance, this is the case when learning a clause on a level greater zero while
839		% a specific SAT variable of this clause has already been propagated on a previous level.
840		update_heuristic_scores(TotalConflicts, Type, T)
841		).
842
843		% v_s + 1
844		bump_heuristic_score_for_type(vsids, _, OldScore, NewScore) :-
845		NewScore is OldScore + 1.
846		% k
847		bump_heuristic_score_for_type(vmtf, TotalConflicts, _, NewScore) :-
848		NewScore is TotalConflicts.
849		% (v_s + k) / 2
850		bump_heuristic_score_for_type(acids, TotalConflicts, OldScore, NewScore) :-
851		NewScore is (OldScore + TotalConflicts) / 2.
852		% v_s + f^(-k), where f is evsids_f_value/1 and it is/was the k-th conflict when finding this clause via conflict analysis
853		bump_heuristic_score_for_type(evsids, TotalConflicts, OldScore, NewScore) :-
854		evsids_f_value(FVal),
855		catch(NewScore is OldScore + FVal**(-TotalConflicts), error(evaluation_error(float_overflow),_), NewScore = 1.35743634973696E+308).
856
857		% Literal Block Distance (LBD) as defined in "Predicting Learnt Clauses Quality in Modern SAT Solvers",
858		% i.e., the amount of different decision levels in a clause.
859		compute_lbd_score(BjClause, LbdScore) :-
860		compute_lbd_score(BjClause, [], LbdScore).
861
862		compute_lbd_score([], Acc, LbdScore) :-
863		length(Acc, LbdScore).
864		compute_lbd_score([(_,(Level,_),_,_)-_-_-_|T], Acc, LbdScore) :-
865		!,
866		ord_add_element(Acc, Level, NewAcc),
867		compute_lbd_score(T, NewAcc, LbdScore).
868
869		%% count_found_conflict(-NewTotal, -NewSinceRestart, -NewSinceReduction).
870		count_found_conflict(Total1, SRes1, SRed1) :-
871		log_conflict,
872		retract(conflict_stats(total(Total), since_restart(SRes), since_reduction(SRed))),
873		Total1 is Total + 1,
874		SRes1 is SRes + 1,
875		SRed1 is SRed + 1,
876		asserta(conflict_stats(total(Total1), since_restart(SRes1), since_reduction(SRed1))).
877
878		%% compute_and_assert_backjump_clause(+SolverEnv, +StateMutable, +StackSize, +ConflictClause).
879		compute_and_assert_backjump_clause(SolverEnv, StateMutable, StackSize, ConflictLevel, ConflictClause) :-
880		compute_and_assert_backjump_clause_get_level(SolverEnv, StateMutable, StackSize, ConflictLevel, ConflictClause, _).
881
882		cnf_to_smt(BoolPred, Smt) :-
883		BoolPred = b(Expr,_,_),
884		cnf_to_smt_e(Expr, Smt).
885
886		cnf_to_smt_e(falsity, b(falsity,pred,[])).
887		cnf_to_smt_e(truth, b(truth,pred,[])).
888		cnf_to_smt_e(conjunct(A,B), Smt) :-
889		cnf_to_smt(A, NA),
890		cnf_to_smt(B, NB),
891		safe_create_texpr(conjunct(NA,NB), pred, [], Smt).
892		cnf_to_smt_e(disjunct(A,B), Smt) :-
893		cnf_to_smt(A, NA),
894		cnf_to_smt(B, NB),
895		safe_create_texpr(disjunct(NA,NB), pred, [], Smt).
896		cnf_to_smt_e(equal(b(identifier(_),_,Info),b(BoolExpr,boolean,_)), Smt) :-
897		member(smt_formula(TSmt), Info),
898		( BoolExpr == boolean_true
899		-> Smt = TSmt
900		; safe_create_texpr(negation(TSmt), pred, [], Smt)
901		).
902
903		/*cnf_to_smt([], _, Acc, SmtFromCnf) :-
904		conjunct_predicates(Acc, SmtFromCnf).
905		cnf_to_smt([Clause|T], PrologSatVarTriple, Acc, SmtFromCnf) :-
906		clause_to_smt(PrologSatVarTriple, Clause, SmtClause),
907		cnf_to_smt(T, PrologSatVarTriple, [SmtClause|Acc], SmtFromCnf).*/
908
909		%clause_to_smt(PlVars, Clause, SmtFormula) :-
910		% clause_to_smt(PlVars, Clause, [], SmtFormula).
911		%
912		%clause_to_smt(_, [], Acc, SmtFormula) :-
913		% disjunct_predicates(Acc, SmtFormula).
914		%clause_to_smt(PlVars, [_-Pol-_-SatVarName|T], Acc, SmtClause) :-
915		% mutdict_get(PlVars, SatVarName, _-SatVarName-TSmtFormula-_),
916		% !,
917		% get_smt_formula_for_sat_pol(TSmtFormula, Pol, SmtFormula),
918		% clause_to_smt(PlVars, T, [SmtFormula|Acc], SmtClause).
919		%clause_to_smt(_, [_-_-SatVarName|_], _, _) :-
920		% add_error_fail(clause_to_smt, 'Unknown SAT variable.', [SatVarName]).
921
922		bump_glue_levels([]).
923		bump_glue_levels([_-_-_-SatVarName|T]) :-
924		( retract(glue_level(SatVarName, GlueLevel,AlreadyBumped))
925		-> NGlueLevel is GlueLevel + 1
926		; NGlueLevel = 1,
927		AlreadyBumped = false
928		),
929		asserta(glue_level(SatVarName,NGlueLevel,AlreadyBumped)),
930		bump_glue_levels(T).
931
932		%% compute_and_assert_backjump_clause_get_level(+SolverEnv, +StateMutable, +StackSize, +ConflictLevel, +ConflictClause, -BjLevel).
933		compute_and_assert_backjump_clause_get_level(SolverEnv, StateMutable, StackSize, ConflictLevel, ConflictClause, BjLevel) :-
934		get_last_decision_level(StateMutable, _),
935		%possibly_discard_learned_clauses, % TODO: adapt to new bj clause handling; yet, forgetting clauses has not shown to be beneficial so far
936		debug_format_sat("~nConflict clause is ~w", [strip-ConflictClause]),
937		debug_format_sat("~nStart CDCL..", []),
938		( (
939		get_backjump_clause_conflict_resolution(SolverEnv, StateMutable, ConflictLevel, ConflictClause, BjClause, BjLevel, BjSatVars, UsedVars),
940		BjLevel \== -1
941		)
942		; add_error_fail(compute_and_assert_backjump_clause_get_level, 'SMT solver\'s conflict resolution failed', [])
943		),
944		debug_format_sat("done.", []),
945		debug_format_sat("Backjump clause is ~w", [strip-BjClause]),
946		debug_format_sat("Backjump level is ~w", [BjLevel]),
947		compute_lbd_score(BjClause, LbdScore),
948		debug_format_sat("LBD Score is ~w", [LbdScore]),
949		( ( glue_bumping(true),
950		LbdScore == 2
951		)
952		-> retract(glue_clauses(Old)),
953		New is Old + 1,
954		asserta(glue_clauses(New)),
955		bump_glue_levels(BjClause)
956		; true
957		),
958		count_found_conflict(NewTotal, NewSinceRestart, _),
959		asserta(backjump_clause(BjLevel, BjClause, LbdScore, BjSatVars, UsedVars, NewTotal)),
960		asserta(backjump_level(BjLevel)),
961		store_recent_stack_size(StackSize),
962		count_learned_clause,
963		possibly_decay_heuristic_values,
964		( \+ clear_lbd_values_or_fail(StateMutable),
965		BjLevel \== 0
966		-> store_recent_lbd_score(LbdScore),
967		update_total_lbd_sum(LbdScore),
968		(random_restart(NewTotal, NewSinceRestart), !; true)
969		; true
970		), !.
971
972		count_learned_clause :-
973		retract(amount_learned_clauses(Old)),
974		New is Old + 1,
975		asserta(amount_learned_clauses(New)).
976
977		%% store_recent_lbd_score(+LbdScore).
978		% The stored list of recent LBDs is a difference list and we insert at the end of the list.
979		% The first LBD is thus the oldest one and removed when exceeding the maximum size
980		% defined by recent_lbd_threshold/1.
981		store_recent_lbd_score(LbdScore) :-
982		retract(recent_lbds_dl(Lbds-Diff, Amount)),
983		glucose_restart_recent_lbds_threshold(Thresh),
984		Diff = [LbdScore|NDiff],
985		( Amount < Thresh
986		-> Amount1 is Amount + 1,
987		asserta(recent_lbds_dl(Lbds-NDiff, Amount1))
988		; Lbds = [_|RLbds],
989		asserta(recent_lbds_dl(RLbds-NDiff, Amount))
990		).
991
992		store_recent_stack_size(StackSize) :-
993		retract(recent_stack_sizes_dl(StackSizes-Diff, Amount)),
994		glucose_restart_trail_threshold(Thresh),
995		Diff = [StackSize|NDiff],
996		( Amount < Thresh
997		-> Amount1 is Amount + 1,
998		asserta(recent_stack_sizes_dl(StackSizes-NDiff, Amount1))
999		; StackSizes = [_|RStackSizes],
1000		asserta(recent_stack_sizes_dl(RStackSizes-NDiff, Amount))
1001		).
1002
1003		%% update_total_lbd_sum(+LbdScore).
1004		update_total_lbd_sum(LbdScore) :-
1005		retract(total_lbd_sum(Old)),
1006		New is Old + LbdScore,
1007		asserta(total_lbd_sum(New)).
1008
1009		%% random_restart(+AmountOfConflicts, +AmountOfConflictsSinceRestart).
1010		% "Randomly" restart after an amount of conflicts since the last restart.
1011		random_restart(_AC, ACR) :-
1012		restart_policy(luby),
1013		random_luby_restart(ACR), !.
1014		random_restart(AC, _ACR) :-
1015		restart_policy(glucose),
1016		random_glucose_restart(AC), !.
1017
1018		do_random_restart :-
1019		log_restart,
1020		retract(restarts(OldR)),
1021		NewR is OldR + 1,
1022		asserta(restarts(NewR)),
1023		retract(backjump_level(_)),
1024		asserta(backjump_level(0)),
1025		retract(conflict_stats(total(Total), _, since_reduction(SRed))),
1026		asserta(conflict_stats(total(Total), since_restart(0), since_reduction(SRed))),
1027		asserta_once(is_restart),
1028		debug_format_sat("~nRandom restart", []).
1029
1030		%% random_glucose_restart(+AmountOfConflicts).
1031		% Restart search if recent_lbds_dl/2 contains exactly glucose_restart_recent_lbds_threshold/1 amount
1032		% of most recent LBDs and RecentAvg * Proportion > TotalAvg is satisfied, i.e., the recently learned clauses'
1033		% LBDs got too large.
1034		random_glucose_restart(AC) :-
1035		total_lbd_sum(TotalLbdSum),
1036		TotalAvg is TotalLbdSum / AC,
1037		recent_lbds_dl(RLbds-[], LbdAmount),
1038		glucose_restart_recent_lbds_threshold(LbdThresh),
1039		LbdAmount == LbdThresh, % queue of recent LBDs is full
1040		sumlist(RLbds, RSum),
1041		RecentAvg is RSum / LbdAmount,
1042		glucose_restart_margin_ratio(Proportion),
1043		debug_format_sat("~nTotalAvg: ~w~nRecentAvg: ~w", [TotalAvg,RecentAvg]),
1044		( RecentAvg * Proportion > TotalAvg
1045		-> do_random_restart,
1046		clear_recent_lbds_state
1047		; true
1048		).
1049
1050		% Favor SAT instances too by possibly clearing the recent LBD queue.
1051		% Assumption: The queue of recent LBDs is full.
1052		clear_lbd_values_or_fail(StateMutable) :-
1053		glucose_restart_trail_threshold(TrailThresh),
1054		glucose_restart_stack_avg_factor(StackSizeFactor),
1055		recent_stack_sizes_dl(StackSizes-[], AmountStackSizes),
1056		AmountStackSizes == TrailThresh, % queue of recent stack sizes on conflict is full
1057		get_full_state(StateMutable, current_stack_size, StackSize),
1058		sumlist(StackSizes, SSum),
1059		StackSizesAvg is SSum / AmountStackSizes,
1060		StackSize > StackSizeFactor * StackSizesAvg,
1061		clear_recent_lbds_state.
1062
1063		clear_recent_lbds_state :-
1064		retract(recent_lbds_dl(_, _)),
1065		asserta(recent_lbds_dl(Diff-Diff, 0)).
1066
1067		%% random_luby_restart(+AmountOfConflictsSinceRestart).
1068		% The amount of conflicts when to restart is defined by the Luby sequence,
1069		% i.e., 1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,.. etc., (cf. "Optimal speedup of Las Vegas algorithms")
1070		% using a unit length of 32 (see luby_counter/1).
1071		random_luby_restart(ACR) :-
1072		restart_policy(luby),
1073		get_next_luby_value(Luby),
1074		!,
1075		( ACR == Luby
1076		-> retract_once(luby_counter(_)),
1077		do_random_restart
1078		; true
1079		).
1080		random_luby_restart(_) :-
1081		add_error_fail(random_restart, 'No more values in predefined Luby sequence', []).
1082
1083		get_next_luby_value(LubyValue) :-
1084		luby_counter(Luby),
1085		luby_restart_unit_length(UnitLength),
1086		LubyValue is UnitLength * Luby,
1087		!.
1088
1089		%% get_sat_solution_exclusion_clauses(+PlVars, -ExclClausesNoRef).
1090		% We exclude SAT solutions when backtracking from finding an SMT solution to find a different assignment.
1091		/*get_sat_solution_exclusion_clauses(PlVars, ExclClausesNoRef) :-
1092		findall(ExclClause,
1093		(exclude_sat_solution_clause(TExclClause), set_variable_references_in_clause(PlVars, TExclClause, ExclClause)),
1094		ExclClausesNoRef), !.*/
1095
1096		%% set_variable_references_in_clauses(+PlVars, +Clauses, -RefClauses).
1097		set_variable_references_in_clauses(_, [], []).
1098		set_variable_references_in_clauses(PlVars, [Clause|T], [RefClause|NT]) :-
1099		set_variable_references_in_clause(PlVars, Clause, RefClause),
1100		set_variable_references_in_clauses(PlVars, T, NT).
1101
1102		%% set_variable_references_in_clause(+PlVars, +Clause, -RefClauses).
1103		% We need to set the correct variable references in a new learned clause
1104		% to trigger co-routines etc.
1105		set_variable_references_in_clause(_, [], Out) :- !, Out = [].
1106		set_variable_references_in_clause(PlVars, [_-Pol-_-Name|T], [StackInfo-Pol-Var-Name|NT]) :-
1107		mutdict_get(PlVars, Name, TVar-Name-_-TStackInfo),
1108		!,
1109		Var = TVar,
1110		StackInfo = TStackInfo,
1111		set_variable_references_in_clause(PlVars, T, NT).
1112		set_variable_references_in_clause(_, [_-_-_-Name|_], _) :-
1113		add_error_fail(set_variable_references_in_clause, 'Cannot set references: unknown SAT variable.', [Name]).
1114
1115		get_from_solver_env(SolverEnv, Key, OutValue) :-
1116		get_from_solver_env_ordered(Key, SolverEnv, Value),
1117		!,
1118		OutValue = Value.
1119		get_from_solver_env(SolverEnv, Key, _) :-
1120		add_error_fail(get_from_solver_env,
1121		'Wrong key or corrupt solver environment in CDCL(T) SAT solver',
1122		[solver_env:SolverEnv,key:Key]).
1123
1124		get_from_solver_env_ordered(sat_vars, [sat_vars:SatVars,_,_,_,_,_], SatVars).
1125		get_from_solver_env_ordered(sat_varnames, [_,sat_varnames:SatVarNames,_,_,_,_], SatVarNames).
1126		get_from_solver_env_ordered(sat_bindings, [_,_,sat_bindings:SatBindings,_,_,_], SatBindings).
1127		get_from_solver_env_ordered(t2b_env, [_,_,_,t2b_env:Env,_,_], Env).
1128		get_from_solver_env_ordered(pl_vars, [_,_,_,_,pl_vars:PlVars,_], PlVars).
1129		get_from_solver_env_ordered(binary_clause_vars, [_,_,_,_,_,binary_clause_vars:VarsFromBinaryClauses], VarsFromBinaryClauses).
1130
1131		bt_asserta(Assertion) :-
1132		asserta(Assertion); (retract(Assertion), !, fail).
1133
1134		bt_retract(Assertion) :-
1135		( retract(Assertion)
1136		-> ( true
1137		; asserta(Assertion),
1138		!,
1139		fail
1140		)
1141		; fail
1142		).
1143
1144		%% get_unsat_core_from_smt_formula(+FullFormula, +LastVarName, -UnsatCore).
1145		% Assumption: unsat core computation only removes constraints and does not deduce new ones.
1146		% Fails if +FullFormula is satisfiable.
1147		get_unsat_core_from_smt_formula(FullFormula, LastVarName, UnsatCore) :-
1148		debug_format_sat("Compute unsat core for: ", [], FullFormula),
1149		preferences:temporary_set_preference(time_out, 25, Change),
1150		call_cleanup(time_out(unsat_chr_core_list_with_auto_time_limit(FullFormula, 30000,
1151		[auto_time_out_factor(180), % we add 80 %
1152		ignore_if_sol_found,
1153		inspect_quantifiers(false)], GlobalRes, CoreList), 30000, TimeoutResult),
1154		reset_temporary_preference(time_out, Change)),
1155		!,
1156		( GlobalRes = solution(_)
1157		-> % the present theory conflict only occurs within the current state of ProB's waitflag store; there is at least one choice point
1158		% in the theory solver which needs to be evaluated; we thus do not learn from this "spurious counterexample" but
1159		% trigger chronological backtracking instead of backjumping
1160		debug_format_sat("Spurious counterexample found. Skip backjumping and use chronological backtracking instead.", []),
1161		fail
1162		; GlobalRes == time_out
1163		-> % ignore core if global result is timeout
1164		TUnsatCore = FullFormula
1165		; TimeoutResult == time_out
1166		-> % don't waste too much time in unsat core computation
1167		debug_format_sat("Canceled unsat core computation due to exceeding a timeout" ,[]),
1168		TUnsatCore = FullFormula
1169		; ( CoreList == []
1170		-> add_error_fail(get_conflict_clause_for_theory_conflict, 'Conflict clause in SMT solving is not a conflict.', [LastVarName])
1171		; conjunct_predicates(CoreList, TUnsatCore)
1172		)
1173		),
1174		debug_format_sat("Computed unsat core with added WD POs: ", [], TUnsatCore),
1175		( remove_wd_pos_introduced_for_cdclt_keep_toplevel(TUnsatCore, UnsatCore)
1176		-> true
1177		; add_error_fail(remove_wd_pos_introduced_for_cdclt_keep_toplevel, 'Removing WD POs for CDCL(T) failed.', [unsat_core_with_wd:TUnsatCore])
1178		),
1179		debug_format_sat("Computed unsat core: ", [], UnsatCore).
1180
1181		%% get_conflict_clause_for_theory_conflict(+LastVarName, +LastVarValue, +SolverEnv, -ConflictClause).
1182		% Translate current sat solution, which is a theory conflict, to the theory and compute
1183		% the (minimum) unsat core. Return the negated theory conflict as a conflict clause.
1184		% Note that an SMT formula passed to the theory solver is always a conjunction and
1185		% thus the negated unsat core is a disjunction (clause).
1186		get_conflict_clause_for_theory_conflict(SolverEnv, LastVarName, LastVarValue, SolverEnv, ConflictClause) :-
1187		( retract(idl_unsat_core(UnsatCore))
1188		-> true
1189		; get_from_solver_env(SolverEnv, sat_bindings, SatBindingsNoLast),
1190		get_from_solver_env(SolverEnv, sat_vars, SatVars),
1191		sat_to_predicate_from_solution(SatBindingsNoLast, SatVars, SmtFormulaNoLast),
1192		findall(bind(PendingName,PendingPol), pending_theory_prop(PendingName,PendingPol), PendingTheoryProps),
1193		sat_to_predicate_from_solution([bind(LastVarName,LastVarValue)|PendingTheoryProps], SatVars, FixedConj),
1194		safe_create_texpr(conjunct(FixedConj,SmtFormulaNoLast), pred, [] , FullFormula),
1195		get_unsat_core_from_smt_formula(FullFormula, LastVarName, UnsatCore)
1196		), !,
1197		find_typed_identifier_uses(UnsatCore, [], UsedIds),
1198		( list_contains_unfixed_deferred_set_id(UsedIds)
1199		-> asserta(unfixed_deferred_set_error)
1200		; true
1201		),
1202		get_conflict_clause_from_unsat_core(UnsatCore, SolverEnv, TConflictClause),
1203		sort(TConflictClause, TTConflictClause), % there can be duplicates due to added top-level WD POs; important to remove
1204		( TTConflictClause = [_]
1205		-> % currently undiscovered static theory contradiction; SAT variable might not be propagated yet if added WD PO
1206		ConflictClause = TTConflictClause
1207		; % remove not propagated top-level WD POs; we enforce WD POs in the theory solver but it can
1208		% be the case that a theory conflict occurs before the WD POs are propagated in the SAT solver
1209		remove_not_propagated(TTConflictClause, LastVarName, ConflictClause)
1210		),
1211		!.
1212
1213		remove_not_propagated([], _, []).
1214		remove_not_propagated([Pol-Var-Name|T], LastVarName, [Pol-Var-Name|NT]) :-
1215		( ground(Var)
1216		; Name == LastVarName
1217		),
1218		!,
1219		remove_not_propagated(T, LastVarName, NT).
1220		remove_not_propagated([_-_-Name|T], LastVarName, NT) :-
1221		debug_format_sat("Remove not propagated SAT variable ~w from conflict clause.", [Name]),
1222		remove_not_propagated(T, LastVarName, NT).
1223
1224		%% get_conflict_clause_from_unsat_core(+UnsatCore, +SolverEnv, -ConflictClause).
1225		get_conflict_clause_from_unsat_core(UnsatCore, SolverEnv, ConflictClause) :-
1226		get_from_solver_env(SolverEnv, sat_vars, SatVars),
1227		get_from_solver_env(SolverEnv, t2b_env, T2BEnv),
1228		get_from_solver_env(SolverEnv, pl_vars, PlVars),
1229		predicate_to_sat(only_reuse, [], SatVars, T2BEnv, UnsatCore, _NewEnv, _, UnsatCoreSat, _NewSatVars),
1230		sat_conj_negate_to_clause(UnsatCoreSat, TConflictClause),
1231		set_variable_references_in_clause(PlVars, TConflictClause, ConflictClause),
1232		!.
1233		get_conflict_clause_from_unsat_core(_, _, _) :-
1234		add_error_fail(get_conflict_clause_from_unsat_core, 'Unsat core to conflict clause failed.', []).
1235
1236		%% get_complete_theory_lemma(+SolverEnv, -TheoryLemmaClause) :-
1237		% Return the complete unsatisfiable SMT formula as a conflict clause.
1238		get_complete_theory_lemma(SolverEnv, TheoryLemmaClause) :-
1239		get_complete_theory_lemma_fixed_binding(SolverEnv, _, _, TheoryLemmaClause).
1240
1241		%% get_complete_theory_lemma_fixed_binding(+SolverEnv, +SatVarName, +SatVarPol, -TheoryLemmaClause).
1242		% Enforce +SatVarName to have +SatVarPol binding. This is important for theory conflicts since the last
1243		% binding has been undone when backtracking. This is not applied if both inputs are variables, e.g., for SAT conflicts.
1244		get_complete_theory_lemma_fixed_binding(SolverEnv, SatVarName, SatVarPol, TheoryLemmaClause) :-
1245		get_from_solver_env(SolverEnv, pl_vars, PlVars),
1246		get_from_solver_env(SolverEnv, sat_bindings, SatBindings),
1247		get_clause_from_negated_ground_bindings(SatBindings, SatVarName, SatVarPol, TTheoryLemmaClause),
1248		set_variable_references_in_clause(PlVars, TTheoryLemmaClause, TheoryLemmaClause), !.
1249
1250		%% get_clause_from_negated_ground_bindings(+SatBindings, +FSatVarName, +FSatVarPol, -TheoryLemmaClause) :-
1251		% FSatVarName: name of SAT variable whose binding should be set to +FSatVarPol
1252		get_clause_from_negated_ground_bindings(SatBindings, FSatVarName, FSatVarPol, TheoryLemmaClause) :-
1253		get_clause_from_negated_ground_bindings(SatBindings, FSatVarName, FSatVarPol, [], TheoryLemmaClause).
1254
1255		get_clause_from_negated_ground_bindings([], _, _, Acc, Acc).
1256		get_clause_from_negated_ground_bindings([bind(SatVarName,_)|T], FSatVarName, FSatVarPol, Acc, TheoryLemmaClause) :-
1257		% theory propagations during grounding are possibly undone in the stack if finding a contradiction during grounding waitflags
1258		% we restore such pending theory propagations here
1259		pending_theory_prop(SatVarName, SatVarPol),
1260		!,
1261		negate_polarity(SatVarPol, NegPol),
1262		get_clause_from_negated_ground_bindings(T, FSatVarName, FSatVarPol, [_-NegPol-_-SatVarName|Acc], TheoryLemmaClause).
1263		get_clause_from_negated_ground_bindings([bind(SatVarName,_)|T], FSatVarName, FSatVarPol, Acc, TheoryLemmaClause) :-
1264		% set fixed polarity
1265		SatVarName == FSatVarName,
1266		!,
1267		negate_polarity(FSatVarPol, NegPol),
1268		get_clause_from_negated_ground_bindings(T, FSatVarName, FSatVarPol, [_-NegPol-_-SatVarName|Acc], TheoryLemmaClause).
1269		get_clause_from_negated_ground_bindings([bind(SatVarName,Pol)|T], FSatVarName, FSatVarPol, Acc, TheoryLemmaClause) :-
1270		ground(Pol),
1271		!,
1272		negate_polarity(Pol, NegPol),
1273		get_clause_from_negated_ground_bindings(T, FSatVarName, FSatVarPol, [_-NegPol-_-SatVarName|Acc], TheoryLemmaClause).
1274		get_clause_from_negated_ground_bindings([_|T], FSatVarName, FSatVarPol, Acc, TheoryLemmaClause) :-
1275		get_clause_from_negated_ground_bindings(T, FSatVarName, FSatVarPol, Acc, TheoryLemmaClause).
1276
1277		%% get_clause_from_ground_bindings(+SatBindings, -TheoryLemmaClause) :-
1278		get_clause_from_ground_bindings(SatBindings, TheoryLemmaClause) :-
1279		get_clause_from_ground_bindings(SatBindings, [], TheoryLemmaClause).
1280
1281		get_clause_from_ground_bindings([], _, _, Acc, Acc).
1282		get_clause_from_ground_bindings([bind(SatVarName,_)|T], FSatVarName, FSatVarPol, Acc, TheoryLemmaClause) :-
1283		% theory propagations during grounding are possibly undone in the stack if finding a contradiction during grounding waitflags
1284		% we restore such pending theory propagations here
1285		pending_theory_prop(SatVarName, SatVarPol),
1286		!,
1287		get_clause_from_ground_bindings(T, FSatVarName, FSatVarPol, [_-SatVarPol-_-SatVarName|Acc], TheoryLemmaClause).
1288		get_clause_from_ground_bindings([bind(SatVarName,Pol)|T], FSatVarName, FSatVarPol, Acc, TheoryLemmaClause) :-
1289		ground(Pol),
1290		!,
1291		get_clause_from_ground_bindings(T, FSatVarName, FSatVarPol, [_-Pol-_-SatVarName|Acc], TheoryLemmaClause).
1292		get_clause_from_ground_bindings([_|T], FSatVarName, FSatVarPol, Acc, TheoryLemmaClause) :-
1293		get_clause_from_ground_bindings(T, FSatVarName, FSatVarPol, Acc, TheoryLemmaClause).
1294
1295		% Fail if no decision has been made so far, i.e., the decision level is set to -1.
1296		get_last_decision_level(StateMutable, Level) :-
1297		get_full_state(StateMutable, cur_level, TLevel),
1298		TLevel > 0,
1299		!,
1300		Level = TLevel.
1301
1302		%negate_polarities([], []).
1303		%negate_polarities([StackInfo-Pol-Var-Name|T], [StackInfo-NPol-Var-Name|NT]) :-
1304		% negate_polarity(Pol, NPol),
1305		% negate_polarities(T, NT).
1306
1307		get_maximum_decision_level([(_,(Level,_),_,_)-_-_-_|T], ConflictLevel) :-
1308		!,
1309		get_maximum_decision_level(T, Level, ConflictLevel).
1310		get_maximum_decision_level([_-_-_-Name|_], _) :-
1311		add_error_fail(get_maximum_decision_level, 'The SAT variable has not been decided yet', [Name]).
1312
1313		get_maximum_decision_level([], Acc, Acc).
1314		get_maximum_decision_level([(_,(Level,_),_,_)-_-_-_|T], Acc, ConflictLevel) :-
1315		!,
1316		( Level > Acc
1317		-> NAcc = Level
1318		; NAcc = Acc
1319		),
1320		get_maximum_decision_level(T, NAcc, ConflictLevel).
1321		get_maximum_decision_level([_-_-_-Name|_], _, _) :-
1322		add_error_fail(get_maximum_decision_level, 'The SAT variable has not been decided yet', [Name]).
1323
1324		get_maximum_decision_level_other_than_current([_], _, _, BjLevel) :-
1325		% zero if learning a unit clause
1326		!,
1327		BjLevel = 0.
1328		get_maximum_decision_level_other_than_current(BjClause, BjLevelAcc, CurLevel, BjLevel) :-
1329		get_maximum_decision_level_other_than_current_not_unit(BjClause, BjLevelAcc, CurLevel, BjLevel).
1330
1331		get_maximum_decision_level_other_than_current_not_unit([], BjLevelAcc, _, BjLevelAcc).
1332		get_maximum_decision_level_other_than_current_not_unit([(_,(Level,_),_,_)-_-_-_|T], BjLevelAcc, CurLevel, BjLevel) :-
1333		( (Level \== CurLevel,
1334		Level > BjLevelAcc
1335		)
1336		-> NBjLevelAcc = Level
1337		; NBjLevelAcc = BjLevelAcc
1338		),
1339		get_maximum_decision_level_other_than_current_not_unit(T, NBjLevelAcc, CurLevel, BjLevel).
1340
1341		%% get_antecedent_assignments(+SolverEnv, +ConflictDLevel, +SatVarName, +RPol, +RPropType, +ROriginalClause, -Antecedent).
1342		get_antecedent_assignments(_, _, SatVarName, _, _, ROriginalClause, Antecedent) :-
1343		is_list(ROriginalClause),
1344		!,
1345		select(_-_-_-SatVarName, ROriginalClause, TAntecedent), !,
1346		Antecedent = TAntecedent.
1347		get_antecedent_assignments(SolverEnv, ConflictDLevel, SatVarName, RPol, theory, ROriginalClause, Antecedent) :-
1348		\+ is_list(ROriginalClause),
1349		!,
1350		explain_theory_propagation(SolverEnv, SatVarName, ConflictDLevel, RPol, OriginalClause),
1351		ROriginalClause = OriginalClause,
1352		select(_-_-_-SatVarName, OriginalClause, TAntecedent), !,
1353		Antecedent = TAntecedent.
1354		get_antecedent_assignments(_, _, SatVarName, _, _, _, _) :-
1355		add_error_fail(get_antecedent_assignments, 'No antecedent assignments since variable has not been propagated.', SatVarName).
1356
1357		%% join_assignments(+A1, +A2, +A2Full, -Joined).
1358		join_assignments([], _, A, A).
1359		join_assignments([StackInfo-Pol-Var-Name|T], A2, A3, Res) :-
1360		( select(_-_-_-Name, A2, A4) % removes dups assuming that A2 has no dups
1361		-> join_assignments(T, A4, A3, Res)
1362		; join_assignments(T, A2, [StackInfo-Pol-Var-Name|A3], Res)
1363		).
1364
1365		%% resolve(+SolverEnv, +TBjClause, +Resolver, +ROriginalClause, -NTBjClause).
1366		% +Resolver is a SAT variable name to resolve next (i.e., expand its antecedent assignments).
1367		resolve(SolverEnv, TBjClause, ConflictDLevel, Resolver, RPol, RPropType, ROriginalClause, NTBjClause) :-
1368		get_antecedent_assignments(SolverEnv, ConflictDLevel, Resolver, RPol, RPropType, ROriginalClause, Antecedent),
1369		join_assignments(Antecedent, TBjClause, TBjClause, TNTBjClause), % important to not have duplicates
1370		select(_-_-_-Resolver, TNTBjClause, NTBjClause).
1371
1372		add_used_vars_to_mutdict([], _).
1373		add_used_vars_to_mutdict([_-_-_-SatVarName|T], VarNamesDict) :-
1374		\+ mutdict_get(VarNamesDict, SatVarName, _),
1375		!,
1376		mutdict_put(VarNamesDict, SatVarName, SatVarName),
1377		add_used_vars_to_mutdict(T, VarNamesDict).
1378		add_used_vars_to_mutdict([_|T], VarNamesDict) :-
1379		add_used_vars_to_mutdict(T, VarNamesDict).
1380
1381		get_variables_used_in_cdcl(ResolvedSoFar, BjClause, UsedVars) :-
1382		add_used_vars_to_mutdict(BjClause, ResolvedSoFar),
1383		mutdict_keys(ResolvedSoFar, UsedVars).
1384
1385		get_variable_names_in_clause([], []).
1386		get_variable_names_in_clause([_-_-_-SatVarName|T], [SatVarName|NT]) :-
1387		get_variable_names_in_clause(T, NT).
1388
1389		% sort in reversed stack order
1390		reversed_stack_sort((_,(DLevel1,ACount1),_,_)-_-_-_, (_,(DLevel2,ACount2),_,_)-_-_-_) :-
1391		ground(DLevel1), ground(DLevel2),
1392		( DLevel1 > DLevel2
1393		-> true
1394		; DLevel1 == DLevel2
1395		-> ACount1 > ACount2
1396		; fail
1397		).
1398
1399		:- dynamic part_of_first_uip/1.
1400
1401		% See https://cca.informatik.uni-freiburg.de/papers/SoerenssonBiere-SAT09.pdf
1402		% Generate the 1-UIP clause. Mark all its literals. Remove those implied variables which have all their antecedent literals marked.
1403		minimize_clause(SolverEnv, ConflictDLevel, BjClause, local, MinBjClause) :-
1404		mark_literals(BjClause),
1405		remove_where_all_antecedent_marked(BjClause, SolverEnv, ConflictDLevel, MinBjClause).
1406		% Generate the 1-UIP clause. Mark its literals. Implied variables in 1-UIP clause are candidates for removal.
1407		% Search implication graph. Start from antecedent literals of candidate. Stop at marked literals or decisions.
1408		% If search always ends at marked literals, the candidate can be removed.
1409		minimize_clause(SolverEnv, ConflictDLevel, BjClause, recursive, MinBjClause) :-
1410		mark_literals(BjClause),
1411		remove_recursively_stop_marked(BjClause, SolverEnv, ConflictDLevel, MinBjClause).
1412
1413		remove_recursively_stop_marked([], _, _, []).
1414		remove_recursively_stop_marked([(PropType,_,_,OriginalClause)-_-Pol-SatVarName|T], SolverEnv, ConflictDLevel, MinBjClause) :-
1415		PropType \== branch,
1416		get_antecedent_assignments(SolverEnv, ConflictDLevel, SatVarName, Pol, PropType, OriginalClause, Antecedent),
1417		samsort(reversed_stack_sort, Antecedent, SAntecedent), % reverse assignment order
1418		recursively_inspect_antecedent(SAntecedent, SolverEnv, ConflictDLevel),
1419		!,
1420		remove_recursively_stop_marked(T, SolverEnv, ConflictDLevel, MinBjClause).
1421		remove_recursively_stop_marked([Lit|T], SolverEnv, ConflictDLevel, [Lit|NT]) :-
1422		remove_recursively_stop_marked(T, SolverEnv, ConflictDLevel, NT).
1423
1424		recursively_inspect_antecedent([], _, _).
1425		recursively_inspect_antecedent([(PropType,_,_,OriginalClause)-_-Pol-SatVarName|T], SolverEnv, ConflictDLevel) :-
1426		recursive_search_stops_at_marked_or_decision(PropType, OriginalClause, Pol, SatVarName, SolverEnv, ConflictDLevel),
1427		recursively_inspect_antecedent(T, SolverEnv, ConflictDLevel).
1428
1429		recursive_search_stops_at_marked_or_decision(_, _, _, SatVarName, _, _) :-
1430		part_of_first_uip(SatVarName),
1431		!.
1432		recursive_search_stops_at_marked_or_decision(PropType, OriginalClause, Pol, SatVarName, SolverEnv, ConflictDLevel) :-
1433		PropType \== branch,
1434		get_antecedent_assignments(SolverEnv, ConflictDLevel, SatVarName, Pol, PropType, OriginalClause, Antecedent),
1435		recursively_inspect_antecedent(Antecedent, SolverEnv, ConflictDLevel).
1436
1437		all_literals_are_marked([]).
1438		all_literals_are_marked([_-_-_-SatVarName|T]) :-
1439		part_of_first_uip(SatVarName),
1440		!,
1441		all_literals_are_marked(T).
1442
1443		remove_where_all_antecedent_marked([], _, _, []).
1444		remove_where_all_antecedent_marked([(PropType,_,_,OriginalClause)-_-Pol-SatVarName|T], SolverEnv, ConflictDLevel, MinBjClause) :-
1445		PropType == unit,
1446		get_antecedent_assignments(SolverEnv, ConflictDLevel, SatVarName, Pol, PropType, OriginalClause, Antecedent),
1447		all_literals_are_marked(Antecedent),
1448		!,
1449		remove_where_all_antecedent_marked(T, SolverEnv, ConflictDLevel, MinBjClause).
1450		remove_where_all_antecedent_marked([Lit|T], SolverEnv, ConflictDLevel, [Lit|NT]) :-
1451		remove_where_all_antecedent_marked(T, SolverEnv, ConflictDLevel, NT).
1452
1453		mark_literals(Lits) :-
1454		retractall(part_of_first_uip(_)),
1455		mark_literals_state(Lits).
1456
1457		mark_literals_state([]).
1458		mark_literals_state([_-_-_-SatVarName|T]) :-
1459		asserta(part_of_first_uip(SatVarName)),
1460		mark_literals_state(T).
1461
1462		%% get_backjump_clause_conflict_resolution(+SolverEnv, +StateMutable, +ConflictLevel, +ConflictClause, -BjClause, -BjLevel, -BjSatVars, -UsedVars).
1463		% In the conflict graph each node corresponds to a variable assignment.
1464		% The predecessors of node x are the antecedent assignments A^w(x) corresponding
1465		% to the unit clause w (in its original form) that led to the propagation of x (logical implications).
1466		% The directed edges from the nodes in A^w(x) to node x are all labeled with w.
1467		% Nodes that have no predecessor correspond to decision/branching assignments
1468		% (cf. GRASP: A Search Algorithm for Propositional Satisfiability, by Marques-Silva and Sakallah).
1469		% As an improvement, we apply first UIP clause learning (cf. Efficient Conflict Driven Learning in a Boolean Satisfiability Solver, Zhang et al.).
1470		% Compute the conflict graph for a conflicting unit-propagation of a variable and extract a backjump clause.
1471		% -UsedVars are the SAT variables used during conflict analysis that are not part of the final bj clause (can be necessary for branching heuristic).
1472		% -BjSatVars are the SAT variables in the final bj clause.
1473		% Notes:
1474		% - the variable references in the returned clause are not yet set
1475		% - we do not create an actual graph but apply Boolean resolution
1476		get_backjump_clause_conflict_resolution(SolverEnv, StateMutable, ConflictLevel, ConflictClause, BjClause, BjLevel, BjSatVars, UsedVars) :-
1477		get_last_decision_level(StateMutable, _),
1478		new_mutdict(ResolvedSoFar),
1479		get_backjump_clause_and_level(SolverEnv, ConflictLevel, ResolvedSoFar, ConflictClause, BjClause, BjLevel, TUsedVars),
1480		get_variable_names_in_clause(BjClause, BjSatVars),
1481		subtract(TUsedVars, BjSatVars, UsedVars).
1482
1483		%% get_backjump_clause_and_level(+SolverEnv, +ConflictDLevel, +ResolvedSoFar, +TBjClause, -BjClause, -BjLevel, -UsedVars).
1484		get_backjump_clause_and_level(SolverEnv, ConflictDLevel, ResolvedSoFar, TBjClause, MinBjClause, BjLevel, UsedVars) :-
1485		get_backjump_clause_and_level_sub(ConflictDLevel, 0, _, TBjClause, Resolver-RPol-RPropType-ROriginalClause, ThisLevelCount),
1486		( ThisLevelCount == 1
1487		-> % break, first UIP
1488		BjClause = TBjClause,
1489		clause_minimization(ClauseMinType),
1490		( ClauseMinType \== none
1491		-> ( minimize_clause(SolverEnv, ConflictDLevel, BjClause, ClauseMinType, MinBjClause), !
1492		; add_error_fail(minimize_clause, 'Clause minimization failed: ', [BjClause])
1493		)
1494		; MinBjClause = BjClause
1495		),
1496		get_maximum_decision_level_other_than_current(MinBjClause, 0, ConflictDLevel, BjLevel),
1497		get_variables_used_in_cdcl(ResolvedSoFar, MinBjClause, UsedVars)
1498		; ground(Resolver),
1499		resolve(SolverEnv, TBjClause, ConflictDLevel, Resolver, RPol, RPropType, ROriginalClause, NToExpand),
1500		mutdict_put(ResolvedSoFar, Resolver, Resolver),
1501		get_backjump_clause_and_level(SolverEnv, ConflictDLevel, ResolvedSoFar, NToExpand, MinBjClause, BjLevel, UsedVars)
1502		).
1503
1504		get_backjump_clause_and_level_sub(_, ThisLevelCountAcc, ResolverAcc-_-RPol-RPropType-ROriginalClause, [], ResolverAcc-RPol-RPropType-ROriginalClause, ThisLevelCountAcc).
1505		get_backjump_clause_and_level_sub(ConflictDLevel, ThisLevelCountAcc, ResolverAcc-RACount-RPol-RPropType-ROriginalClause, [(PropType,(Level,ACount),_,OriginalClause)-Pol-_-SatVarName|T], Resolver, ThisLevelCount) :-
1506		( Level == ConflictDLevel
1507		-> NThisLevelCountAcc is ThisLevelCountAcc + 1
1508		; NThisLevelCountAcc = ThisLevelCountAcc
1509		),
1510		( (
1511		Level == ConflictDLevel,
1512		% unit or theory propagation
1513		PropType \== branch,
1514		% use last assigned literal to resolve next
1515		( var(ResolverAcc)
1516		; ACount > RACount
1517		)
1518		)
1519		-> NResolverAcc = SatVarName-ACount-Pol-PropType-OriginalClause
1520		; NResolverAcc = ResolverAcc-RACount-RPol-RPropType-ROriginalClause
1521		),
1522		get_backjump_clause_and_level_sub(ConflictDLevel, NThisLevelCountAcc, NResolverAcc, T, Resolver, ThisLevelCount).
1523
1524		negate_polarity(pred_true, pred_false).
1525		negate_polarity(pred_false, pred_true).
1526
1527		retractall_once(Assertion) :-
1528		retractall(cdclt_sat_solver:Assertion),
1529		!.
1530
1531		asserta_once(Assertion) :-
1532		call(cdclt_sat_solver:Assertion),
1533		!.
1534		asserta_once(Assertion) :-
1535		asserta(cdclt_sat_solver:Assertion).
1536
1537		b_pred_or_bool_true(X) :- X == truth; X == boolean_true; X == value(pred_true).
1538		b_pred_or_bool_false(X) :- X == falsity; X == boolean_false; X == value(pred_false).
1539
1540		sat_conj_negate_to_clause(Pred, Clause) :-
1541		conjunction_to_list(Pred, List),
1542		maplist(sat_equality_negate_to_literal, List, Clause).
1543
1544		sat_equality_negate_to_literal(b(equal(ID,Pol),pred,_), _-NegPol-_-Name) :-
1545		ID = b(identifier(Name),_,_),
1546		Pol = b(Value,boolean,_),
1547		( b_pred_or_bool_true(Value)
1548		-> NegPol = pred_false
1549		; NegPol = pred_true
1550		).
1551
1552		%%%%% Solver State
1553		create_solver_state(StateMutable) :-
1554		State = [cur_level:0,current_stack_size:0],
1555		create_mutable(solver_state(State), StateMutable).
1556
1557		%% get_full_state(+StateMutable, +Key, -Datum).
1558		% We assume an order of the SolverState to prevent using member.
1559		get_full_state(StateMutable, Key, Datum) :-
1560		get_mutable(solver_state(SolverState), StateMutable),
1561		get_full_state_ordered(Key, SolverState, Datum), !.
1562
1563		get_full_state_ordered(cur_level, [cur_level:CurLevel,_], CurLevel).
1564		get_full_state_ordered(current_stack_size, [_,current_stack_size:Size], Size).
1565
1566		%% delete_from_heuristic(+SatVarName).
1567		delete_from_heuristic(SatVarName) :-
1568		( fibonacci_heap:elm_exists(SatVarName)
1569		-> fibonacci_heap:delete_elm_bt(SatVarName)
1570		; % it can be the case that SatVarName has already been removed
1571		% from the mutable due to coroutines etc.; succeed in this case
1572		true
1573		).
1574
1575		%% update_full_state(+StateMutable, +Key, +Datum).
1576		% We assume an order of the SolverState to prevent using member.
1577		update_full_state(StateMutable, Key, Datum) :-
1578		get_mutable(solver_state(SolverState), StateMutable),
1579		update_full_state_ordered(Key, Datum, SolverState, NewSolverState), !,
1580		update_mutable(solver_state(NewSolverState), StateMutable).
1581
1582		update_full_state_ordered(cur_level, NewDatum, [cur_level:_,B], [cur_level:NewDatum,B]).
1583		update_full_state_ordered(current_stack_size, NewDatum, [A,current_stack_size:_], [A,current_stack_size:NewDatum]).
1584
1585		%% Initialize the dynamic solver state for a specific solver.
1586		init_dynamic_solver_state(SolverName) :-
1587		fibonacci_heap:init,
1588		clean_dynamic_solver_state,
1589		clear_pending_theory_propagations,
1590		asserta(solver_name(SolverName)),
1591		asserta(restarts(0)),
1592		asserta(glue_clauses(0)),
1593		asserta(amount_clause_reductions(0)),
1594		asserta(assignment_count_on_cur_level(0)),
1595		asserta(amount_learned_clauses(0)),
1596		asserta(conflict_stats(total(0), since_restart(0), since_reduction(0))),
1597		asserta(recent_lbds_dl(Diff1-Diff1, 0)),
1598		asserta(recent_stack_sizes_dl(Diff2-Diff2, 0)),
1599		asserta(total_lbd_sum(0)),
1600		init_luby_sequence.
1601
1602		clean_dynamic_solver_state :-
1603		retractall(assignment_timeout_occurred),
1604		retractall(allow_partial_model),
1605		retractall(unfixed_deferred_set_error),
1606		retractall(assignment_count_on_cur_level(_)),
1607		retractall(pending_theory_prop(_,_)),
1608		retractall(glue_clauses(_)),
1609		retractall(glue_level(_,_,_)),
1610		retractall(solver_name(_)),
1611		retractall(restarts(_)),
1612		retractall(is_restart),
1613		retractall(bt_from_smt_solution),
1614		retractall(recent_lbds_dl(_, _)),
1615		retractall(recent_stack_sizes_dl(_, _)),
1616		retractall(saved_phase(_, _)),
1617		retractall(amount_clause_reductions(_)),
1618		retractall(amount_learned_clauses(_)),
1619		retractall(luby_counter(_)),
1620		retractall(exclude_sat_solution_clause(_)),
1621		retractall(total_lbd_sum(_)),
1622		retractall(conflict_stats(_, _, _)),
1623		retractall(idl_unsat_core(_)),
1624		retractall(backjump_level(_)),
1625		retractall(backjump_clause(_, _, _, _, _, _)).
1626
1627		%% Remove dynamically stored unsat core found by the IDL solver.
1628		remove_idl_unsat_core :-
1629		retractall_once(idl_unsat_core(_)).
1630
1631		%% Store an unsat core found by the IDL solver in the SMT solver's dynamic state.
1632		store_idl_unsat_core(Core) :-
1633		assignment_count_on_cur_level(ACount),
1634		ACount > 1, % at least one unit propagation on this level, otherwise just backtrack
1635		retractall_once(idl_unsat_core(_)),
1636		asserta(idl_unsat_core(Core)).
1637
1638		%% Announce backtracking after a solution has been found in order to backtrack to search for another solution.
1639		%% We have to be able to distinguish between backtracking due to not finding a solution or backtracking
1640		%% triggered by the user to find another solution.
1641		announce_bt_from_smt_solution :-
1642		asserta(bt_from_smt_solution).
1643		%%%%%
1644
1645		%% b_to_cnf_safe(+In, +State, -Out).
1646		b_to_cnf_safe(In, State, Out) :-
1647		b_to_cnf(In, State, TOut),
1648		!,
1649		Out = TOut.
1650		b_to_cnf_safe(_, _, _) :-
1651		add_internal_error('B to CNF conversion failed ', cdclt),
1652		fail.
1653
1654		%% b_to_cnf(+In, +State, -Out).
1655		% Accepts predicates with conjunction, disjunction, and equality of SAT variables. No negations.
1656		b_to_cnf(In, State, Out) :-
1657		get_texpr_expr(In, Expr),
1658		b_to_cnf_aux(Expr, State, Res, []),
1659		!,
1660		Res = Out.
1661		b_to_cnf(In, _, _) :-
1662		translate_bexpression(In, PPIn),
1663		!,
1664		add_error_fail(b_to_cnf, 'CNF conversion failed', PPIn).
1665
1666		b_to_cnf(b(Expr,_,_Info), State) -->
1667		!,
1668		b_to_cnf_aux(Expr, State).
1669		b_to_cnf(In, _, _, _) :-
1670		add_error_fail(b_to_cnf, 'Not properly wrapped:', In).
1671
1672		b_to_cnf_aux(X, _) -->
1673		{X == truth}, !,
1674		[].
1675		b_to_cnf_aux(X, _) -->
1676		{X == falsity}, !,
1677		[[]].
1678		b_to_cnf_aux(equal(A,B), State) -->
1679		{get_texpr_expr(B, Expr),
1680		Expr == boolean_true,
1681		get_texpr_expr(A, identifier(Name))},
1682		!,
1683		{member(bind(Name,Res)-StackInfo, State)},
1684		[[StackInfo-pred_true-Res-Name]].
1685		b_to_cnf_aux(equal(A,B), State) -->
1686		{get_texpr_expr(B, Expr),
1687		Expr == boolean_false,
1688		get_texpr_expr(A, identifier(Name)),
1689		member(bind(Name,Res)-StackInfo, State)},
1690		[[StackInfo-pred_false-Res-Name]].
1691		b_to_cnf_aux(disjunct(D1,D2), State) -->
1692		b_to_cnf_disj_aux(D1, D2, State).
1693		b_to_cnf_aux(conjunct(A,B), State) -->
1694		b_to_cnf(A, State),
1695		b_to_cnf(B, State).
1696
1697		b_to_cnf_disj_aux(D1, D2, State) -->
1698		{get_texpr_expr(D1, conjunct(A,B))}, !,
1699		{create_texpr(disjunct(A,D2), pred, [], DJ1),
1700		create_texpr(disjunct(B,D2), pred, [], DJ2)},
1701		b_to_cnf_aux(conjunct(DJ1,DJ2), State).
1702		b_to_cnf_disj_aux(D1, D2, State) -->
1703		{get_texpr_expr(D2, conjunct(A,B))}, !,
1704		{create_texpr(disjunct(D1,A), pred, [], DJ1),
1705		create_texpr(disjunct(D1,B), pred, [], DJ2)},
1706		b_to_cnf_aux(conjunct(DJ1,DJ2), State).
1707		b_to_cnf_disj_aux(D1, D2, State, Res, Acc) :-
1708		b_to_cnf(D1, State, Res1),
1709		b_to_cnf(D2, State, Res2),
1710		!,
1711		( Res1 = []
1712		-> Res = Acc
1713		; Res1 = [[]]
1714		-> append(Res2,Acc,Res)
1715		; Res2 = []
1716		-> Res = Acc
1717		; Res2 = [[]]
1718		-> append(Res1,Acc,Res)
1719		; ( Res1 = [ResD1],
1720		Res2 = [ResD2]
1721		)
1722		-> Res = [Res12|Acc],
1723		append(ResD1, ResD2, Res12)
1724		; join_clauses(Res1,Res2,Res,Acc)
1725		-> true
1726		; add_error_fail(b_to_cnf_disj, 'Cannot join clauses: ', Res1:Res2)
1727		).
1728
1729		join_clauses([], _) --> [].
1730		join_clauses([Clause1|T], Clauses2) -->
1731		join_clauses_aux(Clause1,Clauses2),
1732		join_clauses(T,Clauses2).
1733
1734		join_clauses_aux(_, []) --> [].
1735		join_clauses_aux(Clause1, [Clause2|T]) -->
1736		{append(Clause1, Clause2, NewClause)},
1737		[NewClause],
1738		join_clauses_aux(Clause1, T).
1739
1740
1741		% Used for random restarts.
1742		% First restart is after 32nd conflict, second after additional 32 conflicts,
1743		% third after additional 64 conflicts etc.
1744		init_luby_sequence :-
1745		retractall(luby_counter(_)),
1746		% unit length of 32
1747		% 1,1,2,1,1,2,4,1,1,2,1,1,2,4,8,..
1748		assertz(luby_counter(1)), assertz(luby_counter(1)), assertz(luby_counter(2)), assertz(luby_counter(1)), assertz(luby_counter(1)),
1749		assertz(luby_counter(2)), assertz(luby_counter(4)), assertz(luby_counter(1)), assertz(luby_counter(1)), assertz(luby_counter(2)),
1750		assertz(luby_counter(1)), assertz(luby_counter(1)), assertz(luby_counter(2)), assertz(luby_counter(4)), assertz(luby_counter(8)),
1751		assertz(luby_counter(1)), assertz(luby_counter(1)), assertz(luby_counter(2)), assertz(luby_counter(1)), assertz(luby_counter(1)),
1752		assertz(luby_counter(2)), assertz(luby_counter(4)), assertz(luby_counter(8)), assertz(luby_counter(16)), assertz(luby_counter(1)),
1753		assertz(luby_counter(1)), assertz(luby_counter(2)), assertz(luby_counter(1)), assertz(luby_counter(1)), assertz(luby_counter(2)),
1754		assertz(luby_counter(4)), assertz(luby_counter(8)), assertz(luby_counter(16)), assertz(luby_counter(32)), assertz(luby_counter(1)),
1755		assertz(luby_counter(1)), assertz(luby_counter(2)), assertz(luby_counter(1)), assertz(luby_counter(1)), assertz(luby_counter(2)),
1756		assertz(luby_counter(4)), assertz(luby_counter(8)), assertz(luby_counter(16)), assertz(luby_counter(32)), assertz(luby_counter(64)),
1757		assertz(luby_counter(1)), assertz(luby_counter(1)), assertz(luby_counter(2)), assertz(luby_counter(1)), assertz(luby_counter(1)),
1758		assertz(luby_counter(2)), assertz(luby_counter(4)), assertz(luby_counter(8)), assertz(luby_counter(16)), assertz(luby_counter(32)),
1759		assertz(luby_counter(64)), assertz(luby_counter(128)).
1760
1761		% ----------------
1762
1763		%% simplify_cnf(+CNF, -Simplified).
1764		% Boolean resolution.
1765		simplify_cnf([], []).
1766		simplify_cnf([Clause|T], NewCnf) :-
1767		simplify_clause(Clause, _, Simplified, IsTrue), !,
1768		Simplified \== [], % contradiction if a clause is empty
1769		( IsTrue == true
1770		-> NewCnf = NT % remove true clauses
1771		; NewCnf = [Simplified|NT]
1772		),
1773		simplify_cnf(T, NT).
1774
1775		simplify_clause([], IsTrue, [], IsTrue).
1776		simplify_clause([_-Pol-Var-_|T], IsTrueAcc, NT, IsTrue) :-
1777		ground(Var),
1778		Pol \== Var,
1779		!,
1780		simplify_clause(T, IsTrueAcc, NT, IsTrue).
1781		simplify_clause([StackInfo-Pol-Var-SatVarName|T], IsTrueAcc, [StackInfo-Pol-Var-SatVarName|NT], IsTrue) :-
1782		( Pol == Var
1783		-> IsTrueAcc = true
1784		; true
1785		),
1786		simplify_clause(T, IsTrueAcc, NT, IsTrue).
1787
1788		clause_order(_-_-_-A3, _-_-_-B3) :- A3 @< B3.
1789
1790		%% unit_propagate_cnf(+SolverEnv, +StateMutable, +Clauses, -NewClauses).
1791		% A simple unit propagation, useful to run before reification.
1792		% Removes duplicates from each clause.
1793		% Important to identify all unit clauses, b_to_cnf does not check for unique sat variables in clauses.
1794		% An exhaustive unit-propagation prior to the reification is not beneficial
1795		% since simplifying a CNF is slow compared to using watched literals in sat/4.
1796		% Note: It is important to remove duplicates, e.g., using sort/2. Otherwise, a conflict clause with duplicates
1797		% would lead to failure for first UIP CDCL (first UIP not recognized due to duplicate decision level).
1798		unit_propagate_cnf(SolverEnv, StateMutable, Clauses, NewClauses) :-
1799		unit_prop_clause_sort(true, SolverEnv, StateMutable, Clauses, _, _, TNewClauses), !,
1800		simplify_cnf(TNewClauses, NewClauses).
1801
1802		propagate_unit_clause([StackInfo-Pol-PrologVar-SatVarName], StateMutable, RAcc) :-
1803		( PrologVar == Pol
1804		-> % duplicate unit clause already propagated
1805		true
1806		; PrologVar = Pol,
1807		RAcc = true,
1808		debug_format_sat("deterministic unit propagation of ~w with polarity ~w before reification", [SatVarName,Pol]),
1809		get_next_assignment_count_on_level(ACount),
1810		StackInfo = (unit,(0,ACount),Pol,[_-Pol-PrologVar-SatVarName]),
1811		bt_log_sat_stack(StateMutable, SatVarName, Pol),
1812		log_unit_propagation
1813		).
1814
1815		%% unit_prop_clause_sort(+Sort, +SolverEnv, +StateMutable, +CNF, +RAcc, -Resolved, -NewClauses).
1816		% Removes duplicates from each clause if +Sort is true.
1817		% Logs if a variable has been unit propagated in -Resolved using +RAcc.
1818		unit_prop_clause_sort(_, _, _, [], RAcc, RAcc, []).
1819		unit_prop_clause_sort(Sort, SolverEnv, StateMutable, [[StackInfo-Pol-PrologVar-SatVarName]|T], RAcc, Resolved, NT) :-
1820		propagate_unit_clause([StackInfo-Pol-PrologVar-SatVarName], StateMutable, RAcc),
1821		!,
1822		unit_prop_clause_sort(Sort, SolverEnv, StateMutable, T, RAcc, Resolved, NT).
1823		unit_prop_clause_sort(Sort, SolverEnv, StateMutable, [Clause|T], RAcc, Resolved, NewClauses) :-
1824		( Sort = true
1825		-> remove_dups(Clause, TNewClause),
1826		% clause_order ensures that watched literals are initially set to the same variables for stronger propagation
1827		samsort(clause_order, TNewClause, NewClause)
1828		; NewClause = Clause
1829		),
1830		( NewClause = [_-_-_-_]
1831		-> propagate_unit_clause(NewClause, StateMutable, RAcc),
1832		NewClauses = NT
1833		; NewClauses = [NewClause|NT]
1834		), !,
1835		unit_prop_clause_sort(Sort, SolverEnv, StateMutable, T, RAcc, Resolved, NT).
1836
1837		% ----------------
1838
1839		portray_cnf(Clauses) :- length(Clauses,Len), format('CNF with ~w clauses:~n',[Len]),
1840		maplist(portray_sat_clause,Clauses).
1841
1842		portray_sat_clause(Clause) :- write(' '),maplist(portray_literal,Clause),nl.
1843
1844		portray_literal(pred_false-PrologVar-ID) :- !, format('- ~w(~w) ',[ID,PrologVar]).
1845		portray_literal(pred_true-PrologVar-ID) :- !, format(' ~w(~w) ',[ID,PrologVar]).
1846		portray_literal(Lit) :- format(' *** UNKNOWN: ~w ',[Lit]).
1847
1848		% ----------------
1849
1850		/*
1851		%% static_sat_symmetry_breaking(+Clauses, +SolverEnv, +CurLevelMut, -NewSolverEnv).
1852		% Static SAT symmetry breaking after unit propagation of problem_setup/3 but only once, e.g., not after a restart or bj to level 0
1853		% Can only be used for pure SAT solving.
1854		static_sat_symmetry_breaking(_, SolverEnv, _, NewSolverEnv) :-
1855		static_sat_symmetry_breaking(false),
1856		!,
1857		NewSolverEnv = SolverEnv.
1858		static_sat_symmetry_breaking(Clauses, SolverEnv, CurLevelMut, NewSolverEnv) :-
1859		\+ symmetry_breaking_pred(_, _),
1860		!,
1861		get_symmetry_breaking_predicates(Clauses, SBPsConjNoRef, NewSatVars),
1862		asserta(symmetry_breaking_pred(SBPsConjNoRef,NewSatVars)),
1863		static_sat_symmetry_breaking(Clauses, SolverEnv, CurLevelMut, NewSolverEnv).
1864		static_sat_symmetry_breaking(_, SolverEnv, CurLevelMut, NewSolverEnv) :-
1865		get_asserted_symmetry_breaking_pred(SolverEnv, SBPsConj, NewSolverEnv),
1866		problem_setup(NewSolverEnv, CurLevelMut, SBPsConj).
1867
1868		get_asserted_symmetry_breaking_pred(SolverEnv, SBPsConj, NewSolverEnv) :-
1869		symmetry_breaking_pred(SBPsConjNoRef, NewSatVars),
1870		add_symmetry_breaking_eqs_to_solver_env(NewSatVars, SolverEnv, NewSolverEnv),
1871		get_from_solver_env(NewSolverEnv, pl_vars, PlVars),
1872		set_variable_references_in_clauses(PlVars, SBPsConjNoRef, SBPsConj),
1873		findall(Var, (member(Var, NewSatVars), bt_asserta(heuristic_tuple(Var,1))), _).
1874
1875		%% add_symmetry_breaking_eqs_to_solver_env(+NewSatVars, +SolverEnv, -NewSolverEnv).
1876		% Symmetry breaking might introduce new SAT variables for equalities inbetween cycles of permutations.
1877		% We update the solver environment and create the corresponding SMT formulas for equalities here.
1878		% This is necessary, e.g., if a SAT variable corresponding to an equality introduced
1879		% from symmetry breaking is involved in a conflict.
1880		add_symmetry_breaking_eqs_to_solver_env(NewSatVars, SolverEnv, NewSolverEnv) :-
1881		SolverEnv = [sat_vars:SatVars,sat_varnames:SatVarNames,sat_bindings:SatBindings,t2b_env:Env,pl_vars:PrologSatVarTriple],
1882		add_symmetry_breaking_eqs_to_solver_env(NewSatVars, SatVars, SatVarNames, SatBindings, Env, PrologSatVarTriple, NSatVars, NSatVarNames, NSatBindings, NEnv, NPrologSatVarTriple),
1883		NewSolverEnv = [sat_vars:NSatVars,sat_varnames:NSatVarNames,sat_bindings:NSatBindings,t2b_env:NEnv,pl_vars:NPrologSatVarTriple].
1884
1885		add_symmetry_breaking_eqs_to_solver_env([], SatVars, SatVarNames, SatBindings, Env, PrologSatVarTriple, SatVars, SatVarNames, SatBindings, Env, PrologSatVarTriple).
1886		add_symmetry_breaking_eqs_to_solver_env([NewSatVarName-EqClauses|T], SatVars, SatVarNames, SatBindings, Env, PrologSatVarTriple, NSatVars, NSatVarNames, NSatBindings, NEnv, NPrologSatVarTriple) :-
1887		maplist(clause_to_smt_disjunction(SatVars), EqClauses, EqSmtClauses),
1888		conjunct_predicates(EqSmtClauses, EqSmt1), % all true
1889		maplist(negate_smt_formula, EqSmtClauses, NegEqSmtClauses),
1890		conjunct_predicates(NegEqSmtClauses, EqSmt2), % or all false
1891		EqSmt = b(disjunct(EqSmt1,EqSmt2),pred,[]),
1892		SatVars1 = [b(identifier(NewSatVarName),boolean,[smt_formula(EqSmt),eq_symmetry_break])|SatVars],
1893		SatVarNames1 = [NewSatVarName|SatVarNames],
1894		SatBindings1 = [bind(NewSatVarName,Var)|SatBindings],
1895		PrologSatVarTriple1 = [Var-NewSatVarName-EqSmt|PrologSatVarTriple],
1896		Env1 = [(EqSmt,b(identifier(NewSatVarName),boolean,[]))|Env],
1897		add_symmetry_breaking_eqs_to_solver_env(T, SatVars1, SatVarNames1, SatBindings1, Env1, PrologSatVarTriple1, NSatVars, NSatVarNames, NSatBindings, NEnv, NPrologSatVarTriple).
1898
1899		%clause_to_smt_disjunction(_, [], b(truth,pred,[])).
1900		clause_to_smt_disjunction(SatVars, [Pol-_-SatVarName|T], SmtDisj) :-
1901		get_smt_formula_from_vars_for_sat_pol(SatVars, SatVarName, Pol, SmtFormula),
1902		clause_to_smt_disjunction(SatVars, T, SmtFormula, SmtDisj).
1903
1904		clause_to_smt_disjunction(_, [], Acc, Acc).
1905		clause_to_smt_disjunction(SatVars, [Pol-_-SatVarName|T], Acc, SmtDisj) :-
1906		get_smt_formula_from_vars_for_sat_pol(SatVars, SatVarName, Pol, SmtFormula),
1907		NAcc = b(disjunct(SmtFormula,Acc),pred,[]),
1908		clause_to_smt_disjunction(SatVars, T, NAcc, SmtDisj).
1909		*/
1910
1911		/*
1912		% Remove half of the clauses every "frequency_constant + constant_factor * x" conflicts,
1913		% where x is the amount of clause reductions so far. We keep clauses with a small LBD forever.
1914		possibly_discard_learned_clauses :-
1915		conflict_stats(_, _, since_reduction(SRed)),
1916		cdclt_settings:discard_learned_clauses_frequency_constant(Frequency),
1917		SRed >= Frequency, % first check to improve performance
1918		amount_clause_reductions(Reductions),
1919		cdclt_settings:discard_learned_clauses_constant_factor(Factor),
1920		Threshold is Frequency + Factor * Reductions,
1921		SRed == Threshold,
1922		!,
1923		log_set_of_learned_clauses_reduction,
1924		debug_format_sat("~nDiscard half of learned clauses..", []),
1925		cdclt_settings:discard_clause_greater_lbd(LbdLimit),
1926		amount_learned_clauses(ALC),
1927		Half is ALC // 2,
1928		NReductions is Reductions + 1,
1929		retract(amount_clause_reductions(_)),
1930		asserta(amount_clause_reductions(NReductions)),
1931		discard_half_of_learned_clauses_greater_lbd(0, Half, LbdLimit, Removed),
1932		log_forgotten_clauses(Removed),
1933		retract(amount_learned_clauses(Old)),
1934		New is Old - Removed,
1935		asserta(amount_learned_clauses(New)),
1936		retract(conflict_stats(total(Total), since_restart(SRRed), _)),
1937		asserta(conflict_stats(total(Total), since_restart(SRRed), since_reduction(0))), !.
1938		possibly_discard_learned_clauses.
1939		% Remove half of the clauses learned so far.
1940		% We keep clauses with an LBD smaller than cdclt_settings:discard_clause_greater_lbd/1
1941		% forever. Thus it is not guaranteed that exactly half of the clauses are deleted if
1942		% a lot of high quality clauses have been learned.
1943		discard_half_of_learned_clauses_greater_lbd(C, Half, LbdLimit, Removed) :-
1944		C =< Half,
1945		retract(backjump_clause(BjLevel, BjClause, LbdScore, BjSatVars, UsedVars, AC)),
1946		!,
1947		( LbdScore > LbdLimit
1948		-> C1 is C + 1,
1949		discard_half_of_learned_clauses_greater_lbd(C1, Half, LbdLimit, Removed)
1950		; discard_half_of_learned_clauses_greater_lbd(C, Half, LbdLimit, Removed),
1951		asserta(backjump_clause(BjLevel, BjClause, LbdScore, BjSatVars, UsedVars, AC))
1952		).
1953		discard_half_of_learned_clauses_greater_lbd(C, _, _, C).
1954		*/