Lattice Land Core Library
|
#include <vstore.hpp>
Classes | |
struct | var_dom |
Public Types | |
using | universe_type = U |
using | local_universe = typename universe_type::local_type |
using | allocator_type = Allocator |
using | this_type = VStore<universe_type, allocator_type> |
template<class Alloc > | |
using | tell_type = battery::vector<var_dom<Alloc>, Alloc> |
template<class Alloc > | |
using | ask_type = tell_type<Alloc> |
template<class Alloc = allocator_type> | |
using | snapshot_type = battery::vector<local_universe, Alloc> |
Public Member Functions | |
CUDA | VStore (const this_type &other) |
CUDA | VStore (AType atype, const allocator_type &alloc=allocator_type()) |
CUDA | VStore (AType atype, size_t size, const allocator_type &alloc=allocator_type()) |
template<class R > | |
CUDA | VStore (const VStore< R, allocator_type > &other) |
template<class R , class Alloc2 > | |
CUDA | VStore (const VStore< R, Alloc2 > &other, const allocator_type &alloc=allocator_type()) |
template<class R , class Alloc2 , class... Allocators> | |
CUDA | VStore (const VStore< R, Alloc2 > &other, const AbstractDeps< Allocators... > &deps) |
CUDA | VStore (this_type &&other) |
CUDA allocator_type | get_allocator () const |
CUDA AType | aty () const |
CUDA size_t | vars () const |
CUDA local::BInc | is_top () const |
CUDA local::BDec | is_bot () const |
template<class Alloc = allocator_type> | |
CUDA snapshot_type< Alloc > | snapshot (const Alloc &alloc=Alloc()) const |
template<class Alloc > | |
CUDA this_type & | restore (const snapshot_type< Alloc > &snap) |
template<IKind kind, bool diagnose = false, class F , class Env , class I > | |
CUDA NI bool | interpret (const F &f, Env &env, I &intermediate, IDiagnostics &diagnostics) const |
template<bool diagnose = false, class F , class Env , class Alloc2 > | |
CUDA NI bool | interpret_tell (const F &f, Env &env, tell_type< Alloc2 > &tell, IDiagnostics &diagnostics) const |
template<bool diagnose = false, class F , class Env , class Alloc2 > | |
CUDA NI bool | interpret_ask (const F &f, const Env &env, ask_type< Alloc2 > &ask, IDiagnostics &diagnostics) const |
CUDA const universe_type & | project (AVar x) const |
CUDA const universe_type & | operator[] (int x) const |
CUDA this_type & | tell_top () |
CUDA this_type & | tell (int x, const universe_type &dom) |
template<class Mem > | |
CUDA this_type & | tell (int x, const universe_type &dom, BInc< Mem > &has_changed) |
CUDA this_type & | tell (AVar x, const universe_type &dom) |
template<class Mem > | |
CUDA this_type & | tell (AVar x, const universe_type &dom, BInc< Mem > &has_changed) |
template<class Alloc2 , class Mem > | |
CUDA this_type & | tell (const tell_type< Alloc2 > &t, BInc< Mem > &has_changed) |
template<class Alloc2 > | |
CUDA this_type & | tell (const tell_type< Alloc2 > &t) |
template<class U2 , class Alloc2 , class Mem > | |
CUDA this_type & | tell (const VStore< U2, Alloc2 > &other, BInc< Mem > &has_changed) |
template<class U2 , class Alloc2 > | |
CUDA this_type & | tell (const VStore< U2, Alloc2 > &other) |
CUDA this_type & | dtell_bot () |
template<class U2 , class Alloc2 , class Mem > | |
CUDA this_type & | dtell (const VStore< U2, Alloc2 > &other, BInc< Mem > &has_changed) |
template<class U2 , class Alloc2 , class Mem > | |
CUDA this_type & | dtell (const VStore< U2, Alloc2 > &other) |
template<class Alloc2 > | |
CUDA local::BInc | ask (const ask_type< Alloc2 > &t) const |
CUDA size_t | num_refinements () const |
template<class M > | |
CUDA void | refine (size_t, BInc< M > &) const |
template<class ExtractionStrategy = NonAtomicExtraction> | |
CUDA bool | is_extractable (const ExtractionStrategy &strategy=ExtractionStrategy()) const |
template<class U2 , class Alloc2 > | |
CUDA void | extract (VStore< U2, Alloc2 > &ua) const |
template<class Env > | |
CUDA NI TFormula< typename Env::allocator_type > | deinterpret (const Env &env) const |
CUDA void | print () const |
Static Public Member Functions | |
static CUDA this_type | bot (AType atype=UNTYPED, const allocator_type &alloc=allocator_type{}) |
static CUDA this_type | top (AType atype=UNTYPED, const allocator_type &alloc=allocator_type{}) |
template<class Env > | |
static CUDA this_type | bot (Env &env, const allocator_type &alloc=allocator_type{}) |
template<class Env > | |
static CUDA this_type | top (Env &env, const allocator_type &alloc=allocator_type{}) |
Static Public Attributes | |
static constexpr const bool | is_abstract_universe = false |
static constexpr const bool | sequential = universe_type::sequential |
static constexpr const bool | is_totally_ordered = false |
static constexpr const bool | preserve_bot = true |
static constexpr const bool | preserve_top = true |
static constexpr const bool | preserve_join = universe_type::preserve_join |
static constexpr const bool | preserve_meet = universe_type::preserve_meet |
static constexpr const bool | injective_concretization = universe_type::injective_concretization |
static constexpr const bool | preserve_concrete_covers = universe_type::preserve_concrete_covers |
static constexpr const char * | name = "VStore" |
Friends | |
template<class U2 , class Alloc2 > | |
class | VStore |
The variable store abstract domain is a domain transformer built on top of an abstract universe U
. Concretization function: \( \gamma(\rho) := \bigcap_{x \in \pi(\rho)} \gamma_{U_x}(\rho(x)) \). The top element is smashed and the equality between two stores is represented by the following equivalence relation, for two stores \( S \) and \( T \): \( S \equiv T \Leftrightarrow \forall{x \in \mathit{Vars}},~S(x) = T(x) \lor \exists{x \in \mathit{dom}(S)},\exists{y \in \mathit{dom}(T)},~S(x) = \top \land T(y) = \top \). Intuitively, it means that either all elements are equal or both stores have a top element, in which case they "collapse" to the top element, and are considered equal.
The bottom element is the element \( \langle \bot, \ldots \rangle \), that is an infinite number of variables initialized to bottom. In practice, we cannot represent infinite collections, so we represent bottom either as the empty collection or with a finite number of bottom elements. Any finite store \( \langle x_1, \ldots, x_n \rangle \) should be seen as the concrete store \( \langle x_1, \ldots, x_n, \bot, \ldots \rangle \).
This semantics has implication when joining or merging two elements. For instance, \( \langle 1 \rangle.\mathit{dtell}(\langle \bot, 4 \rangle) \) will be equal to bottom, in that case represented by \( \langle \bot \rangle \).
Template parameters:
U
is the type of the abstract universe.Allocator
is the allocator of the underlying array of universes. using lala::VStore< U, Allocator >::universe_type = U |
using lala::VStore< U, Allocator >::local_universe = typename universe_type::local_type |
using lala::VStore< U, Allocator >::allocator_type = Allocator |
using lala::VStore< U, Allocator >::this_type = VStore<universe_type, allocator_type> |
using lala::VStore< U, Allocator >::tell_type = battery::vector<var_dom<Alloc>, Alloc> |
using lala::VStore< U, Allocator >::ask_type = tell_type<Alloc> |
using lala::VStore< U, Allocator >::snapshot_type = battery::vector<local_universe, Alloc> |
|
inline |
|
inline |
Initialize an empty store.
|
inline |
|
inline |
|
inline |
|
inline |
Copy the vstore other
in the current element. deps
can be empty and is not used besides to get the allocator (since this abstract domain does not have dependencies).
|
inline |
|
inline |
|
inline |
|
inline |
Returns the number of variables currently represented by this abstract element.
|
inlinestatic |
|
inlinestatic |
A special symbolic element representing top.
|
inlinestatic |
|
inlinestatic |
|
inline |
true
if at least one element is equal to top in the store, false
otherwise.
|
inline |
The bottom element of a store of n
variables is when all variables are at bottom, or the store is empty. We do not expect to use this operation a lot, so its complexity is linear in the number of variables.
|
inline |
Take a snapshot of the current variable store.
|
inline |
|
inline |
|
inline |
The store of variables lattice expects a formula with a single variable (including existential quantifiers) that can be handled by the abstract universe U
.
Variables must be existentially quantified before a formula containing variables can be interpreted. Variables are immediately assigned to an index of VStore
and initialized to \( \bot_U \). Shadowing/redeclaration of variables with existential quantifier is not supported. The variable mapping is added to the environment only if the interpretation succeeds.
There is a small quirk: different stores might be produced if quantifiers do not appear in the same order. This is because we attribute the first available index to variables when interpreting the quantifier. In that case, the store will only be equivalent modulo the env
structure.
|
inline |
Similar to interpret_tell
but do not support existential quantifier and therefore leaves env
unchanged.
|
inline |
The projection must stay const, otherwise the user might tell new information in the universe, but we need to know in case we reach top
.
|
inline |
See note on projection.
|
inline |
|
inline |
Given an abstract variable v
, tell(VID(v), dom)
will update the domain of this variable with the new information dom
. This tell
method follows PCCP's model, but the variable x
must already be initialized in the store.
|
inline |
This tell
method follows PCCP's model, but the variable x
must already be initialized in the store.
|
inline |
This tell
method follows PCCP's model, but the variable x
must already be initialized in the store.
|
inline |
This tell
method follows PCCP's model, but the variable x
must already be initialized in the store.
|
inline |
This tell method can grow the store if required, and therefore do not satisfy the PCCP model. /!\ It should not be used in parallel.
|
inline |
This tell method can grow the store if required, and therefore do not satisfy the PCCP model. /!\ It should not be used in parallel.
|
inline |
Precondition: other
must be smaller or equal in size than the current store.
|
inline |
Precondition: other
must be smaller or equal in size than the current store.
|
inline |
|
inline |
Precondition: other
must be smaller or equal in size than the current store.
|
inline |
Precondition: other
must be smaller or equal in size than the current store.
|
inline |
true
when we can deduce the content of t
from the current domain. For instance, if we have in the store x = [0..10]
, we can deduce x = [-1..11]
but we cannot deduce x = [5..8]
.
|
inline |
|
inline |
|
inline |
An abstract element is extractable when it is not equal to top. If the strategy is atoms
, we check the domains are singleton.
|
inline |
Whenever this
is different from top
, we extract its data into ua
.
is_extractable()
must be true
. For now, we suppose VStore is only used to store under-approximation, I'm not sure yet how we would interact with over-approximation.
|
inline |
|
inline |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |
|
staticconstexpr |