#include <string_refinement.h>

Inheritance diagram for string_refinementt:

Collaboration diagram for string_refinementt:

Classes
struct	configt

struct	infot
	string_refinementt constructor arguments More...

Public Member Functions
	string_refinementt (const infot &)

std::string	decision_procedure_text () const override

exprt	get (const exprt &expr) const override
	Evaluates the given expression in the valuation found by string_refinementt::dec_solve. More...

void	set_to (const exprt &expr, bool value) override
	Record the constraints to ensure that the expression is true when the boolean is true and false otherwise. More...

decision_proceduret::resultt	dec_solve () override
	Main decision procedure of the solver. More...

Public Member Functions inherited from bv_refinementt
	bv_refinementt (const infot &info)

Public Member Functions inherited from bv_pointerst
	bv_pointerst (const namespacet &_ns, propt &_prop)

void	post_process () override

Public Member Functions inherited from boolbvt
	boolbvt (const namespacet &_ns, propt &_prop)

virtual const bvt &	convert_bv (const exprt &expr)

void	print_assignment (std::ostream &out) const override

void	clear_cache () override

virtual bool	literal (const exprt &expr, std::size_t bit, literalt &literal) const

mp_integer	get_value (const bvt &bv)

mp_integer	get_value (const bvt &bv, std::size_t offset, std::size_t width)

const boolbv_mapt &	get_map () const

Public Member Functions inherited from arrayst
	arrayst (const namespacet &_ns, propt &_prop)

literalt	record_array_equality (const equal_exprt &expr)

void	record_array_index (const index_exprt &expr)

Public Member Functions inherited from equalityt
	equalityt (const namespacet &_ns, propt &_prop)

virtual literalt	equality (const exprt &e1, const exprt &e2)

void	post_process () override

Public Member Functions inherited from prop_conv_solvert
	prop_conv_solvert (const namespacet &_ns, propt &_prop)

virtual	~prop_conv_solvert ()=default

void	print_assignment (std::ostream &out) const override

virtual tvt	l_get (literalt a) const override

void	set_frozen (literalt a) override

bool	has_set_assumptions () const override

void	set_all_frozen () override

literalt	convert (const exprt &expr) override

bool	is_in_conflict (literalt l) const override
	determine whether a variable is in the final conflict More...

bool	has_is_in_conflict () const override

virtual bool	literal (const exprt &expr, literalt &literal) const

const cachet &	get_cache () const

const symbolst &	get_symbols () const

void	set_time_limit_seconds (uint32_t lim) override

virtual void	set_frozen (literalt a)

virtual void	set_frozen (const bvt &)

Public Member Functions inherited from prop_convt
	prop_convt (const namespacet &_ns)

virtual	~prop_convt ()

literalt	operator() (const exprt &expr)

virtual void	set_frozen (const bvt &)

Public Member Functions inherited from decision_proceduret
	decision_proceduret (const namespacet &_ns)

virtual	~decision_proceduret ()

void	set_to_true (const exprt &expr)

void	set_to_false (const exprt &expr)

resultt	operator() ()

Public Member Functions inherited from messaget
virtual void	set_message_handler (message_handlert &_message_handler)

message_handlert &	get_message_handler ()

	messaget ()

	messaget (const messaget &other)

messaget &	operator= (const messaget &other)

	messaget (message_handlert &_message_handler)

virtual	~messaget ()

mstreamt &	get_mstream (unsigned message_level) const

mstreamt &	error () const

mstreamt &	warning () const

mstreamt &	result () const

mstreamt &	status () const

mstreamt &	statistics () const

mstreamt &	progress () const

mstreamt &	debug () const

void	conditional_output (mstreamt &mstream, const std::function< void(mstreamt &)> &output_generator) const
	Generate output to `mstream` using `output_generator` if the configured verbosity is at least as high as that of `mstream`. More...

Private Types
typedef bv_refinementt	supert

Private Member Functions
	string_refinementt (const infot &, bool)

void	add_lemma (const exprt &lemma, bool simplify_lemma=true)
	Add the given lemma to the solver. More...

Private Attributes
const configt	config_

std::size_t	loop_bound_

string_constraint_generatort	generator

std::set< exprt >	seen_instances

string_axiomst	axioms

std::vector< exprt >	current_constraints

index_set_pairt	index_sets

union_find_replacet	symbol_resolve

std::vector< equal_exprt >	equations

string_dependenciest	dependencies

Related Functions
(Note that these are not member functions.)
std::vector< exprt >	instantiate_not_contains (const string_not_contains_constraintt &axiom, const std::set< std::pair< exprt, exprt >> &index_pairs, const string_constraint_generatort &generator)
	Instantiates a quantified formula representing `not_contains` by substituting the quantifiers and generating axioms. More...

Additional Inherited Members
Public Types inherited from boolbvt
enum	unbounded_arrayt { unbounded_arrayt::U_NONE, unbounded_arrayt::U_ALL, unbounded_arrayt::U_AUTO }

Public Types inherited from arrayst
typedef equalityt	SUB

Public Types inherited from prop_conv_solvert
typedef std::map< irep_idt, literalt >	symbolst

typedef std::unordered_map< exprt, literalt, irep_hash >	cachet

Public Types inherited from decision_proceduret
enum	resultt { resultt::D_SATISFIABLE, resultt::D_UNSATISFIABLE, resultt::D_ERROR }

Public Types inherited from messaget
enum	message_levelt { M_ERROR =1, M_WARNING =2, M_RESULT =4, M_STATUS =6, M_STATISTICS =8, M_PROGRESS =9, M_DEBUG =10 }

Static Public Member Functions inherited from messaget
static unsigned	eval_verbosity (const std::string &user_input, const message_levelt default_verbosity, message_handlert &dest)
	Parse a (user-)provided string as a verbosity level and set it as the verbosity of dest. More...

static mstreamt &	eom (mstreamt &m)

static mstreamt &	endl (mstreamt &m)

Public Attributes inherited from boolbvt
unbounded_arrayt	unbounded_array

boolbv_widtht	boolbv_width

Public Attributes inherited from prop_conv_solvert
bool	use_cache = true

bool	equality_propagation = true

bool	freeze_all = false

Protected Types inherited from bv_pointerst
typedef boolbvt	SUB

typedef std::list< postponedt >	postponed_listt

Protected Types inherited from boolbvt
typedef arrayst	SUB

typedef std::unordered_map< const exprt, bvt, irep_hash >	bv_cachet

typedef std::list< quantifiert >	quantifier_listt

typedef std::vector< std::size_t >	offset_mapt

Protected Types inherited from arrayst
enum	lazy_typet { lazy_typet::ARRAY_ACKERMANN, lazy_typet::ARRAY_WITH, lazy_typet::ARRAY_IF, lazy_typet::ARRAY_OF, lazy_typet::ARRAY_TYPECAST }

typedef std::list< array_equalityt >	array_equalitiest

typedef std::set< exprt >	index_sett

typedef std::map< std::size_t, index_sett >	index_mapt

Protected Types inherited from equalityt
typedef std::unordered_map< const exprt, unsigned, irep_hash >	elementst

typedef std::map< std::pair< unsigned, unsigned >, literalt >	equalitiest

typedef std::map< unsigned, exprt >	elements_revt

typedef std::unordered_map< const typet, typestructt, irep_hash >	typemapt

Protected Member Functions inherited from bv_refinementt
void	post_process_arrays () override
	generate array constraints More...

bvt	convert_mult (const exprt &expr) override

bvt	convert_div (const div_exprt &expr) override

bvt	convert_mod (const mod_exprt &expr) override

bvt	convert_floatbv_op (const exprt &expr) override

void	set_assumptions (const bvt &_assumptions) override

Protected Member Functions inherited from bv_pointerst
void	encode (std::size_t object, bvt &bv)

virtual bvt	convert_pointer_type (const exprt &expr)

virtual void	add_addr (const exprt &expr, bvt &bv)

literalt	convert_rest (const exprt &expr) override

bvt	convert_bitvector (const exprt &expr) override
	Converts an expression into its gate-level representation and returns a vector of literals corresponding to the outputs of the Boolean circuit. More...

exprt	bv_get_rec (const bvt &bv, const std::vector< bool > &unknown, std::size_t offset, const typet &type) const override

bool	convert_address_of_rec (const exprt &expr, bvt &bv)

void	offset_arithmetic (bvt &bv, const mp_integer &x)

void	offset_arithmetic (bvt &bv, const mp_integer &factor, const exprt &index)

void	offset_arithmetic (bvt &bv, const mp_integer &factor, const bvt &index_bv)

void	do_postponed (const postponedt &postponed)

Protected Member Functions inherited from boolbvt
virtual bool	boolbv_set_equality_to_true (const equal_exprt &expr)

void	conversion_failed (const exprt &expr, bvt &bv)

bvt	conversion_failed (const exprt &expr)

bool	type_conversion (const typet &src_type, const bvt &src, const typet &dest_type, bvt &dest)

virtual literalt	convert_bv_rel (const exprt &expr)

virtual literalt	convert_typecast (const typecast_exprt &expr)
	conversion from bitvector types to boolean More...

virtual literalt	convert_reduction (const unary_exprt &expr)

virtual literalt	convert_onehot (const unary_exprt &expr)

virtual literalt	convert_extractbit (const extractbit_exprt &expr)

virtual literalt	convert_overflow (const exprt &expr)

virtual literalt	convert_equality (const equal_exprt &expr)

virtual literalt	convert_verilog_case_equality (const binary_relation_exprt &expr)

virtual literalt	convert_ieee_float_rel (const exprt &expr)

virtual literalt	convert_quantifier (const exprt &expr)

virtual bvt	convert_index (const exprt &array, const mp_integer &index)
	index operator with constant index More...

virtual bvt	convert_index (const index_exprt &expr)

virtual bvt	convert_bswap (const bswap_exprt &expr)

virtual bvt	convert_byte_extract (const byte_extract_exprt &expr)

virtual bvt	convert_byte_update (const byte_update_exprt &expr)

virtual bvt	convert_constraint_select_one (const exprt &expr)

virtual bvt	convert_if (const if_exprt &expr)

virtual bvt	convert_struct (const struct_exprt &expr)

virtual bvt	convert_array (const exprt &expr)

virtual bvt	convert_vector (const exprt &expr)

virtual bvt	convert_complex (const exprt &expr)

virtual bvt	convert_complex_real (const exprt &expr)

virtual bvt	convert_complex_imag (const exprt &expr)

virtual bvt	convert_lambda (const exprt &expr)

virtual bvt	convert_let (const let_exprt &)

virtual bvt	convert_array_of (const array_of_exprt &expr)

virtual bvt	convert_union (const union_exprt &expr)

virtual bvt	convert_bv_typecast (const typecast_exprt &expr)

virtual bvt	convert_add_sub (const exprt &expr)

virtual bvt	convert_floatbv_typecast (const floatbv_typecast_exprt &expr)

virtual bvt	convert_member (const member_exprt &expr)

virtual bvt	convert_with (const exprt &expr)

virtual bvt	convert_update (const exprt &expr)

virtual bvt	convert_case (const exprt &expr)

virtual bvt	convert_cond (const exprt &expr)

virtual bvt	convert_shift (const binary_exprt &expr)

virtual bvt	convert_bitwise (const exprt &expr)

virtual bvt	convert_unary_minus (const unary_exprt &expr)

virtual bvt	convert_abs (const abs_exprt &expr)

virtual bvt	convert_concatenation (const exprt &expr)

virtual bvt	convert_replication (const replication_exprt &expr)

virtual bvt	convert_bv_literals (const exprt &expr)

virtual bvt	convert_constant (const constant_exprt &expr)

virtual bvt	convert_extractbits (const extractbits_exprt &expr)

virtual bvt	convert_symbol (const exprt &expr)

virtual bvt	convert_bv_reduction (const unary_exprt &expr)

virtual bvt	convert_not (const not_exprt &expr)

virtual bvt	convert_power (const binary_exprt &expr)

virtual bvt	convert_function_application (const function_application_exprt &expr)

virtual exprt	make_bv_expr (const typet &type, const bvt &bv)

virtual exprt	make_free_bv_expr (const typet &type)

void	convert_with (const typet &type, const exprt &op1, const exprt &op2, const bvt &prev_bv, bvt &next_bv)

void	convert_with_bv (const exprt &op1, const exprt &op2, const bvt &prev_bv, bvt &next_bv)

void	convert_with_array (const array_typet &type, const exprt &op1, const exprt &op2, const bvt &prev_bv, bvt &next_bv)

void	convert_with_union (const union_typet &type, const exprt &op2, const bvt &prev_bv, bvt &next_bv)

void	convert_with_struct (const struct_typet &type, const exprt &op1, const exprt &op2, const bvt &prev_bv, bvt &next_bv)

void	convert_update_rec (const exprt::operandst &designator, std::size_t d, const typet &type, std::size_t offset, const exprt &new_value, bvt &bv)

virtual exprt	bv_get_unbounded_array (const exprt &) const

exprt	bv_get (const bvt &bv, const typet &type) const

exprt	bv_get_cache (const exprt &expr) const

bool	is_unbounded_array (const typet &type) const override

void	post_process_quantifiers ()

offset_mapt	build_offset_map (const struct_typet &src)

Protected Member Functions inherited from arrayst
void	add_array_constraint (const lazy_constraintt &lazy, bool refine=true)
	adds array constraints (refine=true...lazily for the refinement loop) More...

void	add_array_constraints ()

void	add_array_Ackermann_constraints ()

void	add_array_constraints_equality (const index_sett &index_set, const array_equalityt &array_equality)

void	add_array_constraints (const index_sett &index_set, const exprt &expr)

void	add_array_constraints_if (const index_sett &index_set, const if_exprt &exprt)

void	add_array_constraints_with (const index_sett &index_set, const with_exprt &expr)

void	add_array_constraints_update (const index_sett &index_set, const update_exprt &expr)

void	add_array_constraints_array_of (const index_sett &index_set, const array_of_exprt &exprt)

void	update_index_map (bool update_all)

void	update_index_map (std::size_t i)
	merge the indices into the root More...

void	collect_arrays (const exprt &a)

void	collect_indices ()

void	collect_indices (const exprt &a)

Protected Member Functions inherited from equalityt
virtual literalt	equality2 (const exprt &e1, const exprt &e2)

virtual void	add_equality_constraints ()

virtual void	add_equality_constraints (const typestructt &typestruct)

Protected Member Functions inherited from prop_conv_solvert
virtual bool	get_bool (const exprt &expr, tvt &value) const
	get a boolean value from counter example if not valid More...

virtual literalt	convert_bool (const exprt &expr)

virtual bool	set_equality_to_true (const equal_exprt &expr)

virtual literalt	get_literal (const irep_idt &symbol)

virtual void	ignoring (const exprt &expr)

Protected Attributes inherited from bv_refinementt
configt	config_

Protected Attributes inherited from bv_pointerst
pointer_logict	pointer_logic

unsigned	object_bits

unsigned	offset_bits

unsigned	bits

postponed_listt	postponed_list

Protected Attributes inherited from boolbvt
bv_utilst	bv_utils

functionst	functions

boolbv_mapt	map

bv_cachet	bv_cache

quantifier_listt	quantifier_list

numbering< irep_idt >	string_numbering

Protected Attributes inherited from arrayst
array_equalitiest	array_equalities

union_find< exprt >	arrays

index_mapt	index_map

bool	lazy_arrays

bool	incremental_cache

std::list< lazy_constraintt >	lazy_array_constraints

std::map< exprt, bool >	expr_map

std::set< std::size_t >	update_indices

Protected Attributes inherited from equalityt
typemapt	typemap

Protected Attributes inherited from prop_conv_solvert
bool	post_processing_done = false

symbolst	symbols

cachet	cache

propt &	prop

Protected Attributes inherited from decision_proceduret
const namespacet &	ns

Protected Attributes inherited from messaget
message_handlert *	message_handler

mstreamt	mstream

Detailed Description

Definition at line 34 of file string_refinement.h.

Member Typedef Documentation

◆ supert

typedef bv_refinementt string_refinementt::supert

private

Definition at line 63 of file string_refinement.h.

Constructor & Destructor Documentation

◆ string_refinementt() [1/2]

string_refinementt::string_refinementt ( const infot & info )

explicit

Definition at line 174 of file string_refinement.cpp.

◆ string_refinementt() [2/2]

string_refinementt::string_refinementt	(	const infot &	info,
		bool
	)

private

Definition at line 166 of file string_refinement.cpp.

Member Function Documentation

◆ add_lemma()

void string_refinementt::add_lemma	(	const exprt &	lemma,
		bool	simplify_lemma = `true`
	)

private

Add the given lemma to the solver.

Parameters

lemma	a Boolean expression
simplify_lemma	whether the lemma should be simplified before being given to the underlying solver.

Definition at line 843 of file string_refinement.cpp.

References CHARACTER_FOR_UNKNOWN, prop_conv_solvert::convert(), current_constraints, messaget::debug(), exprt::depth_begin(), exprt::depth_end(), messaget::eom(), format(), from_integer(), exprt::is_true(), propt::l_set_to_true(), decision_proceduret::ns, prop_conv_solvert::prop, union_find_replacet::replace_expr(), seen_instances, simplify(), symbol_resolve, and to_array_type().

Referenced by dec_solve().

◆ dec_solve()

decision_proceduret::resultt string_refinementt::dec_solve ( )

overridevirtual

Main decision procedure of the solver.

Looks for a valuation of variables compatible with the constraints that have been given to set_to so far.

The decision procedure initiated by string_refinementt::dec_solve is composed of several steps detailed below.

Symbol resolution

Pointer symbols which are set to be equal by constraints, are replaced by an single symbol in the solver. The symbol_solvert object used for this substitution is constructed by generate_symbol_resolution_from_equations(const std::vector<equal_exprt>&,const namespacet&,messaget::mstreamt&). All these symbols are then replaced using replace_symbols_in_equations(const union_find_replacet &, std::vector<equal_exprt> &).

Conversion to first order formulas:

Each string primitive is converted to a list of first order formulas by the function substitute_function_applications_in_equations(std::vector<equal_exprt>&,string_constraint_generatort&). These formulas should be unquantified or be either a string_constraintt or a string_not_contains_constraintt. The constraints corresponding to each primitive can be found by following the links in section String primitives.

Since only arrays appear in the string constraints, during the conversion to first order formulas, pointers are associated to arrays. The string_constraint_generatort object keeps track of this association. It can either be set manually using the primitives cprover_associate_array_to_pointer or a fresh array is created.

Refinement loop

We use super_dec_solve and super_get to denote the methods of the underlying solver (bv_refinementt by default). The refinement loop relies on functions string_refinementt::check_axioms which returns true when the set of quantified constraints q is satisfied by the valuation given bysuper_get and string_refinementt::instantiate which gives propositional formulas implied by a string constraint. If the following algorithm returns SAT or UNSAT, the given constraints are SAT or UNSAT respectively:

is_SAT(unquantified_constraints uq, quantified_constraints q)
{
  cur <- uq;
  while(limit--) > 0
  {
    if(super_dec_solve(cur)==SAT)
    {
      if(check_axioms(q, super_get))
      else
        for(axiom in q)
          cur.add(instantiate(axiom));
        return SAT;
    }
    else
      return UNSAT;
  }
  return ERROR;
}

Returns: resultt::D_SATISFIABLE if the constraints are satisfiable, resultt::D_UNSATISFIABLE if they are unsatisfiable, resultt::D_ERROR if the limit of iteration was reached.

Reimplemented from bv_refinementt.

Definition at line 605 of file string_refinement.cpp.

References string_dependenciest::add_constraints(), add_lemma(), add_node(), string_constraint_generatort::array_pool, axioms, can_cast_expr< function_application_exprt >(), check_axioms(), string_dependenciest::clean_cache(), string_constraint_generatort::clear_constraints(), config_, index_set_pairt::current, current_constraints, decision_proceduret::D_ERROR, decision_proceduret::D_SATISFIABLE, DATA_INVARIANT, messaget::debug(), bv_refinementt::dec_solve(), dependencies, display_index_set(), messaget::eom(), equations, messaget::error(), format(), string_constraint_generatort::fresh_symbol, generate_instantiations(), generate_symbol_resolution_from_equations(), generator, array_poolt::get_arrays_of_pointers(), string_constraint_generatort::get_constraints(), string_constraint_generatort::get_lemmas(), string_constraint_generatort::get_not_contains_constraints(), index_sets, index_type(), initial_index_set(), is_valid_string_constraint(), loop_bound_, make_char_array_pointer_associations(), string_axiomst::not_contains, decision_proceduret::ns, string_dependenciest::output_dot(), union_find_replacet::replace_expr(), replace_symbols_in_equations(), boolbvt::set_to(), string_identifiers_resolution_from_equations(), string_refinement_invariantt, symbol_resolve, to_array_type(), union_find_replacet::to_vector(), string_axiomst::universal, update_index_set(), string_refinementt::configt::use_counter_example, and string_constraint_generatort::witness.

◆ decision_procedure_text()

std::string string_refinementt::decision_procedure_text ( ) const

inlineoverridevirtual

Reimplemented from bv_refinementt.

Definition at line 54 of file string_refinement.h.

References prop_conv_solvert::prop, and propt::solver_text().

◆ get()

exprt string_refinementt::get ( const exprt & expr ) const

overridevirtual

Evaluates the given expression in the valuation found by string_refinementt::dec_solve.

Arrays of characters are interpreted differently from the result of supert::get: values are propagated to the left to fill unknown.

Parameters

expr	an expression

Returns: evaluated expression

Reimplemented from boolbvt.

Definition at line 1971 of file string_refinement.cpp.

References index_exprt::array(), string_constraint_generatort::array_pool, CHARACTER_FOR_UNKNOWN, interval_sparse_arrayt::concretize(), if_exprt::cond(), messaget::debug(), dependencies, string_dependenciest::eval(), expr_dynamic_cast(), expr_try_dynamic_cast(), if_exprt::false_case(), from_integer(), generator, boolbvt::get(), get_array(), string_constraint_generatort::get_created_strings(), array_poolt::get_length(), id2string(), index_exprt::index(), INVARIANT, is_char_array_type(), is_char_type(), array_string_exprt::length(), decision_proceduret::ns, interval_sparse_arrayt::of_expr(), union_find_replacet::replace_expr(), typet::subtype(), symbol_resolve, to_array_string_expr(), if_exprt::true_case(), exprt::type(), and UNREACHABLE.

◆ set_to()

void string_refinementt::set_to	(	const exprt &	expr,
		bool	value
	)

overridevirtual

Record the constraints to ensure that the expression is true when the boolean is true and false otherwise.

Parameters

expr	an expression of type `bool`
value	the boolean value to set it to

Reimplemented from boolbvt.

Definition at line 282 of file string_refinement.cpp.

References prop_conv_solvert::equality_propagation, equations, has_char_array_subexpr(), irept::id(), INVARIANT, decision_proceduret::ns, PRECONDITION, boolbvt::set_to(), to_equal_expr(), and exprt::type().

Friends And Related Function Documentation

◆ instantiate_not_contains()

std::vector< exprt > instantiate_not_contains	(	const string_not_contains_constraintt &	axiom,
		const std::set< std::pair< exprt, exprt >> &	index_pairs,
		const string_constraint_generatort &	generator
	)

Parameters

[in]	axiom	the axiom to instantiate
[in]	index_pairs	pair of indexes for `axiom.s0()`and `axiom.s1()`
[in]	generator	generator to be used to get `axiom`'s witness

Returns: the lemmas produced through instantiation

union_find_replacet string_refinementt::symbol_resolve

private

Definition at line 83 of file string_refinement.h.

Referenced by add_lemma(), dec_solve(), and get().

The documentation for this class was generated from the following files:

solvers/refinement/string_refinement.h
solvers/refinement/string_constraint_instantiation.cpp
solvers/refinement/string_refinement.cpp

Classes

Public Member Functions

Private Types

Private Member Functions

Private Attributes

Related Functions

Additional Inherited Members

Detailed Description

Member Typedef Documentation

◆ supert

Constructor & Destructor Documentation

◆ string_refinementt() [1/2]

◆ string_refinementt() [2/2]

Member Function Documentation

◆ add_lemma()

◆ dec_solve()

Symbol resolution

Conversion to first order formulas:

Refinement loop

◆ decision_procedure_text()

◆ get()

◆ set_to()

Friends And Related Function Documentation

◆ instantiate_not_contains()

Member Data Documentation

◆ axioms

◆ config_

◆ current_constraints

◆ dependencies

◆ equations

◆ generator

◆ index_sets

◆ loop_bound_

◆ seen_instances

◆ symbol_resolve