bap-std 2.3.0 · OCaml Package

Table.

Tables are used to partition memory region into a set of non-intersecting areas. Each area is associated with arbitrary value of type 'a bound to the type of the table.

All operations over tables are purely applicative, i.e. there is no observable side-effects. Although, they employ some kind of caching underneath the hood, so that they perform better if they're build once and used many times.

Tables can be also linked. For example, if you have two tables mapping the same memory region to a different sets of values, you can create a mapping from one set of values to another. See link function for mode details.

type 'a t = 'a table

val sexp_of_t : 
  ('a -> Ppx_sexp_conv_lib.Sexp.t) ->
  'a t ->
  Ppx_sexp_conv_lib.Sexp.t

type 'a hashable = 'a Core_kernel.Hashtbl.Hashable.t

val empty : 'a t

creates an empty table

val singleton : mem -> 'a -> 'a t

creates a table containing one bindins

val add : 'a t -> mem -> 'a -> 'a t Core_kernel.Or_error.t

add table mem v returns a new table with added mapping from a mem region mem to a data value v

val remove : 'a t -> mem -> 'a t

returns a new table with all mappings from the mem region mem removed

val change : 
  'a t ->
  mem ->
  f:
    ((mem * 'a) seq ->
      [ `rebind of mem * 'a | `update of (mem * 'a) -> 'a | `remove | `ignore ]) ->
  'a t

change tab mem ~f function f is applied to a set of all memory regions that intersects with mem. If function f evaluates to `remap (new_mem,y) then all memory regions that have had intersections with mem will be removed from the new map and memory region new_mem will be mapped to y. If f evaluates to `remove, then the regions will be removed, and nothing will be added. If it evaluates to `skip then the table will be returned unchanged. Intersections are passed sorted in an ascending order.

val length : 'a t -> int

length table returns a number of entries in the table

val find : 'a t -> mem -> 'a option

find table mem finds an element mapped to the memory region mem

val find_addr : 'a t -> addr -> (mem * 'a) option

find_addr tab addr finds a memory region that contains a specified addr

val intersections : 'a t -> mem -> (mem * 'a) seq

intersections table mem returns all mappings in a table that have intersections with mem

val fold_intersections : 
  'a t ->
  mem ->
  init:'b ->
  f:(mem -> 'a -> 'b -> 'b) ->
  'b

fold_intersections table mem folds over all regions intersecting with mem

val has_intersections : 'a t -> mem -> bool

has_intersections tab mem is true iff some portion of mem is is already mapped in tab.

val mem : _ t -> mem -> bool

mem table mem is true if table contains mem region mem

val next : 'a t -> mem -> (mem * 'a) option

next table elt returns element next to elt, if any

val prev : 'a t -> mem -> (mem * 'a) option

next table elt returns element preceding to elt, if any

val min : 'a t -> (mem * 'a) option

min tab return the lowest binding

val max : 'a t -> (mem * 'a) option

max tab return the highest binding

type ('a, 'm) r

Relation multiplicity. For a given type 'a creates type 'm

Table relations

val many : ('a, 'a seq) r

0..*

val at_least_one : ('a, 'a * 'a seq) r

val one : ('a, 'a) r

1..1

val maybe_one : ('a, 'a option) r

0..1

link relation t t1 t2 takes two tables and returns a mapping from elements of one table to elements of other table.

Parameter t specifies a hashable typeclass of the type 'a. If type 'a implements Hashable interface, then you can obtain it with hashable function, e.g. Int.hashable with return the appropriate type class. If 'a doesn't implement Hashable, then it can be implemented manually.

Relation specifies the multiplicity of the relation between entities from table t1 to entities from table t2, and is summarized below:

one_to_many means that a particular region from table t1 can span several memory regions from table t2. Example: segments to symbols relation.

one_to_one means that for each value of type 'a there is exactly one value of type 'b. This relation should be used with caution, since it is quantified over _all_ values of type 'a. Indeed, it should be used only for cases, when it can be guaranteed, that it is impossible to create such value of type 'b, that has no correspondence in table t2. Otherwise, one_to_maybe_one relation should be used. Example: llvm machine code to assembly string relation.

one_to_maybe_one means that for each value in table t1 there exists at most one value in table t2. Example: function to symbol relation.

Examples

let mc_of_insn  = link one_to:one Insn.hashable insns mcs
let syms_of_sec = link one_to:many Sec.hashable  secs syms

val link : one_to:('b, 'r) r -> 'a hashable -> 'a t -> 'b t -> 'a -> 'r

val rev_map : 
  one_to:(mem, 'r) r ->
  'a hashable ->
  'a t ->
  ('a -> 'r) Core_kernel.Or_error.t

rev_map arity t tab creates a reverse mapping from values of typeclass t stored in table tab to memory regions.

Note. not every mapping is reversible, for example, trying to obtain a reverse of surjective mapping as a one-to-one mapping will result in an error. But surjective mappings can be reversed using ~one_to:many mapping. A particular example of surjective mapping is symbol tables, in a case when functions can occupy several non-contiguous regions of memory.

For example, to create a mapping from a function symbol to sequence of memory regions with it code:

rev_map one_to:many Sym.hashable tab

type 'a ranged = ?start:mem -> ?until:mem -> 'a

Iterators

This section provides a common set of iterators. Note: name iterator is used in a functional meaning, i.e., an iterator is a function that takes a data structure and another function, and applies it to all elements in some manner.

All iterators share some common part of interface that was lifted to a 'a ranged type. When you see

('a t -> f:('a -> bool) -> bool) ranged

just mentally substitute it with:

?start -> ?until -> 'a t -> f:('a -> bool) -> bool.

In other words 'f ranged just prepends ?start -> ?until -> to function with type 'f (do not forget that 'f can be an arrow type).

start and until parameters narrows iteration to some subset of table. If they are unspecified then iteration would be performed on all table entries in an ascending order of addresses. If they are specified, then if start <= until, then iteration will be performed in the same order but on a specified subset. In the case, when start > until, iteration will be performed in a decreasing order.

val exists : ('a t -> f:('a -> bool) -> bool) ranged

exists ~start ~until ~f table checks if at least one element of table satisfies the predicate f.

val for_all : ('a t -> f:('a -> bool) -> bool) ranged

for_all ~start ~until ~f table checks if all elements of table satisfies the predicate f.

val existsi : ('a t -> f:(mem -> 'a -> bool) -> bool) ranged

existsi ~start ~until ~f table is like exists, but also passes the memory as an argument.

val for_alli : ('a t -> f:(mem -> 'a -> bool) -> bool) ranged

for_alli ~start ~until ~f table is like for_all, but also passes the memory as an argument.

val count : ('a t -> f:('a -> bool) -> int) ranged

count ~start ~until ~f table returns the number of elements table that satisfy the predicate p

val find_if : ('a t -> f:('a -> bool) -> 'a option) ranged

find_if ~start ~until ~f table returns the first element of table that satisfies the predicate p or None if no elements satisfied

val find_map : ('a t -> f:('a -> 'b option) -> 'b option) ranged

find_map ~start ~until ~f table returns the first evaluation of f that returns Some or None if f always returns None

val fold : ('a t -> init:'b -> f:('a -> 'b -> 'b) -> 'b) ranged

fold ~start ~until ~init ~f table returns a fold over table in form f elt_n ( ... (f elt_2 (f (elt_1 acc))) ... )

val iter : ('a t -> f:('a -> unit) -> unit) ranged

iter ~start ~until ~f table applies function f in turn to elements of table

val find_mapi : ('a t -> f:(mem -> 'a -> 'b option) -> 'b option) ranged

find_mapi ~start ~until ~f table is like find_map, but also passes the memory as an argument.

val foldi : ('a t -> init:'b -> f:(mem -> 'a -> 'b -> 'b) -> 'b) ranged

foldi ~start ~until ~f table is like fold, but also passes the memory as an argument.

val iteri : ('a t -> f:(mem -> 'a -> unit) -> unit) ranged

ieri ~start ~until ~f table is like iter, but also passes the memory as an argument.

val map : ('a t -> f:('a -> 'b) -> 'b t) ranged

map ~start ~until ~f table applies f to elements of table and builds new table with results returned by f

val mapi : ('a t -> f:(mem -> 'a -> 'b) -> 'b t) ranged

mapi ~start ~until ~f table is like map, but also passes the memory as an argument.

val filter : ('a t -> f:('a -> bool) -> 'a t) ranged

filter ~start ~until ~f table removes all mappings from table that doesn't satisfies the predicate f

val filter_map : ('a t -> f:('a -> 'b option) -> 'b t) ranged

filter_map ~start ~until ~f table return a subtable of table containing only elements for which f returns Some

val filteri : ('a t -> f:(mem -> 'a -> bool) -> 'a t) ranged

filteri ~start ~until ~f table is like filter, but also passes the memory as an argument.

val filter_mapi : ('a t -> f:(mem -> 'a -> 'b option) -> 'b t) ranged

filter_mapi ~start ~until ~f table is like filter_map, but also passes the memory as an argument.

val to_sequence : ('a t -> (mem * 'a) seq) ranged

to_sequence ~start ~until table converts the table to a sequence of key-value pairs.

val regions : ('a t -> mem seq) ranged

regions table returns in an ascending order of addresses all memory regions mapped in a table

val elements : ('a t -> 'a seq) ranged

elements table returns in an ascending order of addresses all elements mapped in a table

val pp : 
  (Stdlib.Format.formatter -> 'a -> unit) ->
  Stdlib.Format.formatter ->
  'a t ->
  unit

pp printer - creates a printer for table from value printer

package bap-std

Table relations

Examples