Module type Map_lattice.MapSet_Lattice

A lattice structure on top of maps from keys to values and sets of keys. The maps and the sets have their own lattice structure (see abstract_interp.ml for the lattice of sets). The sets are implicitly considered as maps binding all their keys to top. Any map is included in the set of its keys (and in any larger set).

type set
type map
type t =
  1. | Top of set * Origin.t
  2. | Map of map
include Datatype.S_with_collections with type t := t
include Datatype.S with type t := t
include Datatype.S_no_copy with type t := t
include Datatype.Ty with type t := t
module Set : Datatype.Set with type elt = t
module Map : Datatype.Map with type key = t
module Hashtbl : Datatype.Hashtbl with type key = t
include Lattice with type t := t
include Lattice_type.Bounded_Join_Semi_Lattice with type t := t
include Lattice_type.Join_Semi_Lattice with type t := t

datatype of element of the lattice

include Datatype.S with type t := t
include Datatype.S_no_copy with type t := t
include Datatype.Ty with type t := t
val ty : t Type.t
val name : string

Unique name of the datatype.

val descr : t Descr.t

Datatype descriptor.

val packed_descr : Structural_descr.pack

Packed version of the descriptor.

val reprs : t list

List of representants of the descriptor.

val equal : t -> t -> bool

Equality: same spec than Stdlib.(=).

val compare : t -> t -> int

Comparison: same spec than Stdlib.compare.

val hash : t -> int

Hash function: same spec than Hashtbl.hash.

val pretty : Stdlib.Format.formatter -> t -> unit

Pretty print each value in an user-friendly way.

val mem_project : (Project_skeleton.t -> bool) -> t -> bool

mem_project f x must return true iff there is a value p of type Project.t in x such that f p returns true.

val copy : t -> t

Deep copy: no possible sharing between x and copy x.

val join : t -> t -> t

over-approximation of union

val is_included : t -> t -> bool

is first argument included in the second?

include Lattice_type.With_Narrow with type t := t
val narrow : t -> t -> t

over-approximation of intersection

include Lattice_type.With_Under_Approximation with type t := t

under-approximation of union

val meet : t -> t -> t

under-approximation of intersection

include Lattice_type.With_Intersects with type t := t
val intersects : t -> t -> bool

intersects t1 t2 returns true iff the intersection of t1 and t2 is non-empty.

include Lattice_type.With_Diff with type t := t
val diff : t -> t -> t

diff t1 t2 is an over-approximation of t1-t2. t2 must be an under-approximation or exact.

val bottom : t
val top : t
type key
type v
val add : key -> v -> t -> t

add key v t binds the value v to key in t. If t is a set, it adds key to the set. If v is bottom, then it removes the key from t instead.

val find : key -> t -> v

find key t returns the value bound to key in t. It returns Value.top if t is a set that contains key. It returns Value.bottom if key does not belong to t.

val find_lonely_key : t -> key * v

If t is a singleton map binding k to v, then returns the pair (k,v).

  • raises Not_found

    otherwise.

val split : key -> t -> v * t

split key t is equivalent to find key t, add key bottom t.

val inject : key -> v -> t

Returns the singleton map binding key to v.

val get_keys : t -> set

Returns the set of keys in t.

val filter_keys : (key -> bool) -> t -> t
val map : (v -> v) -> t -> t
val fold_keys : (key -> 'a -> 'a) -> t -> 'a -> 'a
val fold : (key -> v -> 'a -> 'a) -> t -> 'a -> 'a
val cached_fold : cache_name:string -> temporary:bool -> f:(key -> v -> 'a) -> projection:(key -> v) -> joiner:('a -> 'a -> 'a) -> empty:'a -> t -> 'a
val for_all : (key -> v -> bool) -> t -> bool

for_all p t checks if all binding of t satisfy p . Always false if t is top.

val exists : (key -> v -> bool) -> t -> bool

exists p t checks if one binding of t satisfies p. Always true if t is top.

val pretty_debug : Stdlib.Format.formatter -> t -> unit