cprover
string_refinementt Class Referencefinal

#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 bvtconvert_bv (const exprt &expr, const optionalt< std::size_t > expected_width=nullopt)
 
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_maptget_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
 
bool literal (const symbol_exprt &expr, literalt &literal) const
 
const cachetget_cache () const
 
const symbolstget_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_handlertget_message_handler ()
 
 messaget ()
 
 messaget (const messaget &other)
 
messagetoperator= (const messaget &other)
 
 messaget (message_handlert &_message_handler)
 
virtual ~messaget ()
 
mstreamtget_mstream (unsigned message_level) const
 
mstreamterror () const
 
mstreamtwarning () const
 
mstreamtresult () const
 
mstreamtstatus () const
 
mstreamtstatistics () const
 
mstreamtprogress () const
 
mstreamtdebug () const
 
void conditional_output (mstreamt &mstream, const std::function< void(mstreamt &)> &output_generator) const
 Generate output to message_stream using output_generator if the configured verbosity is at least as high as that of message_stream. 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< exprtseen_instances
 
string_axiomst axioms
 
std::vector< exprtcurrent_constraints
 
index_set_pairt index_sets
 
union_find_replacet symbol_resolve
 
std::vector< equal_exprtequations
 
string_dependenciest dependencies
 

Related Functions

(Note that these are not member functions.)

std::vector< exprtinstantiate_not_contains (const string_not_contains_constraintt &axiom, const std::set< std::pair< exprt, exprt >> &index_pairs, const std::unordered_map< string_not_contains_constraintt, symbol_exprt > &witnesses)
 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, literaltsymbolst
 
typedef std::unordered_map< exprt, literalt, irep_hashcachet
 
- 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 commandt command (unsigned c)
 Create an ECMA-48 SGR (Select Graphic Rendition) command. More...
 
- 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
 
- Static Public Attributes inherited from messaget
static eomt eom
 
static const commandt reset
 return to default formatting, as defined by the terminal More...
 
static const commandt red
 render text with red foreground color More...
 
static const commandt green
 render text with green foreground color More...
 
static const commandt yellow
 render text with yellow foreground color More...
 
static const commandt blue
 render text with blue foreground color More...
 
static const commandt magenta
 render text with magenta foreground color More...
 
static const commandt cyan
 render text with cyan foreground color More...
 
static const commandt bright_red
 render text with bright red foreground color More...
 
static const commandt bright_green
 render text with bright green foreground color More...
 
static const commandt bright_yellow
 render text with bright yellow foreground color More...
 
static const commandt bright_blue
 render text with bright blue foreground color More...
 
static const commandt bright_magenta
 render text with bright magenta foreground color More...
 
static const commandt bright_cyan
 render text with bright cyan foreground color More...
 
static const commandt bold
 render text with bold font More...
 
static const commandt faint
 render text with faint font More...
 
static const commandt italic
 render italic text More...
 
static const commandt underline
 render underlined text More...
 
- Protected Types inherited from bv_pointerst
typedef boolbvt SUB
 
typedef std::list< postponedtpostponed_listt
 
- Protected Types inherited from boolbvt
typedef arrayst SUB
 
typedef std::unordered_map< const exprt, bvt, irep_hashbv_cachet
 
typedef std::list< quantifiertquantifier_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_equalitytarray_equalitiest
 
typedef std::set< exprtindex_sett
 
typedef std::map< std::size_t, index_settindex_mapt
 
- Protected Types inherited from equalityt
typedef std::unordered_map< const exprt, unsigned, irep_hashelementst
 
typedef std::map< std::pair< unsigned, unsigned >, literaltequalitiest
 
typedef std::map< unsigned, exprtelements_revt
 
typedef std::unordered_map< const typet, typestructt, irep_hashtypemapt
 
- Protected Member Functions inherited from bv_refinementt
void post_process_arrays () override
 generate array constraints More...
 
bvt convert_mult (const mult_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 quantifier_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 vector_exprt &expr)
 
virtual bvt convert_complex (const complex_exprt &expr)
 
virtual bvt convert_complex_real (const complex_real_exprt &expr)
 
virtual bvt convert_complex_imag (const complex_imag_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 cond_exprt &)
 
virtual bvt convert_shift (const binary_exprt &expr)
 
virtual bvt convert_bitwise (const exprt &expr)
 
virtual bvt convert_unary_minus (const unary_minus_exprt &expr)
 
virtual bvt convert_abs (const abs_exprt &expr)
 
virtual bvt convert_concatenation (const concatenation_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_idtstring_numbering
 
- Protected Attributes inherited from arrayst
array_equalitiest array_equalities
 
union_find< exprtarrays
 
index_mapt index_map
 
bool lazy_arrays
 
bool incremental_cache
 
std::list< lazy_constrainttlazy_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
 
proptprop
 
- Protected Attributes inherited from decision_proceduret
const namespacetns
 
- Protected Attributes inherited from messaget
message_handlertmessage_handler
 
mstreamt mstream
 

Detailed Description

Definition at line 58 of file string_refinement.h.

Member Typedef Documentation

◆ supert

Definition at line 84 of file string_refinement.h.

Constructor & Destructor Documentation

◆ string_refinementt() [1/2]

string_refinementt::string_refinementt ( const infot info)
explicit

Definition at line 175 of file string_refinement.cpp.

◆ string_refinementt() [2/2]

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

Definition at line 167 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
lemmaa Boolean expression
simplify_lemmawhether the lemma should be simplified before being given to the underlying solver.

Definition at line 849 of file string_refinement.cpp.

◆ 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 610 of file string_refinement.cpp.

◆ decision_procedure_text()

std::string string_refinementt::decision_procedure_text ( ) const
inlineoverridevirtual

Reimplemented from bv_refinementt.

Definition at line 75 of file string_refinement.h.

◆ 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
expran expression
Returns
evaluated expression

Reimplemented from boolbvt.

Definition at line 1961 of file string_refinement.cpp.

◆ 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
expran expression of type bool
valuethe boolean value to set it to

Reimplemented from boolbvt.

Definition at line 286 of file string_refinement.cpp.

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 std::unordered_map< string_not_contains_constraintt, symbol_exprt > &  witnesses 
)
related

Instantiates a quantified formula representing not_contains by substituting the quantifiers and generating axioms.

Parameters
[in]axiomthe axiom to instantiate
[in]index_pairspair of indexes for axiom.s0()and axiom.s1()
[in]witnessesaxiom's witnesses for non containment
Returns
the lemmas produced through instantiation

Definition at line 21 of file string_constraint_instantiation.cpp.

Member Data Documentation

◆ axioms

string_axiomst string_refinementt::axioms
private

Definition at line 95 of file string_refinement.h.

◆ config_

const configt string_refinementt::config_
private

Definition at line 88 of file string_refinement.h.

◆ current_constraints

std::vector<exprt> string_refinementt::current_constraints
private

Definition at line 98 of file string_refinement.h.

◆ dependencies

string_dependenciest string_refinementt::dependencies
private

Definition at line 108 of file string_refinement.h.

◆ equations

std::vector<equal_exprt> string_refinementt::equations
private

Definition at line 106 of file string_refinement.h.

◆ generator

string_constraint_generatort string_refinementt::generator
private

Definition at line 90 of file string_refinement.h.

◆ index_sets

index_set_pairt string_refinementt::index_sets
private

Definition at line 103 of file string_refinement.h.

◆ loop_bound_

std::size_t string_refinementt::loop_bound_
private

Definition at line 89 of file string_refinement.h.

◆ seen_instances

std::set<exprt> string_refinementt::seen_instances
private

Definition at line 93 of file string_refinement.h.

◆ symbol_resolve

union_find_replacet string_refinementt::symbol_resolve
private

Definition at line 104 of file string_refinement.h.


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