package bap-std

  1. Overview
  2. Docs
package bap-std
Legend:
Library
Module
Module type
Parameter
Class
Class type

Tries on BIL.

Bil provides two prefix tries trees.

The default one is not normalized and will compare bil statements literally. This means that comparison is sensitive to variable names and immediate values. Depending on your context it may be find or not. For example, two SP variables may compare as different if one of them was obtained from different compilation (and met the other one through some persistant storage, e.g., file on hard disk). Moreover, BIL obtained from different lifters will have different names for the same registers. All this issues are addressed in normalized Trie.

type normalized_bil
val normalize : ?subst:(exp * exp) list -> stmt list -> normalized_bil

normalize ?subst bil normalize BIL. If subst is provided, then substitute each occurence of the fst expression to the snd expression before the normalization. The effect of normalization is the following:

1. All immediate values are compared equal 2. All variables are compared nominally 3. BIL is simplified to reduce the syntactic differences (but the comparison is still syntactic, and (x + 2) will be compared differently to (2 + x).

module Normalized : Trie.S with type key = normalized_bil
include Trie.S with type key = stmt list
type 'a t

trie can store arbitrary data

include sig ... end
val t_of_sexp : (Sexplib.Sexp.t -> 'a) -> Sexplib.Sexp.t -> 'a t
val sexp_of_t : ('a -> Sexplib.Sexp.t) -> 'a t -> Sexplib.Sexp.t
val bin_t : 'a Core_kernel.Std.Bin_prot.Type_class.t -> 'a t Core_kernel.Std.Bin_prot.Type_class.t
val bin_read_t : 'a Core_kernel.Std.Bin_prot.Read.reader -> 'a t Core_kernel.Std.Bin_prot.Read.reader
val __bin_read_t__ : 'a Core_kernel.Std.Bin_prot.Read.reader -> (int -> 'a t) Core_kernel.Std.Bin_prot.Read.reader
val bin_reader_t : 'a Core_kernel.Std.Bin_prot.Type_class.reader -> 'a t Core_kernel.Std.Bin_prot.Type_class.reader
val bin_size_t : 'a Core_kernel.Std.Bin_prot.Size.sizer -> 'a t Core_kernel.Std.Bin_prot.Size.sizer
val bin_write_t : 'a Core_kernel.Std.Bin_prot.Write.writer -> 'a t Core_kernel.Std.Bin_prot.Write.writer
val bin_writer_t : 'a Core_kernel.Std.Bin_prot.Type_class.writer -> 'a t Core_kernel.Std.Bin_prot.Type_class.writer
type key = stmt list

a key type that is used to lookup data

val create : unit -> 'a t

create () creates new empty trie

val add : 'a t -> key:key -> data:'a -> unit

add trie ~key ~data adds data associated with key, if trie already has some data associated with the key, then it will be overwritten

val change : 'a t -> key -> ('a option -> 'a option) -> unit

change trie key f if trie has data associated with key then f will be called with Some data, otherwise it will be called with None. If f returns None then there will be no data associated with key, if f returns Some thing, then thing will be bound to key

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

find trie key finds data associated with key

val walk : 'a t -> key -> init:'b -> f:('b -> 'a option -> 'b) -> 'b

walk trie key ~init ~f walks down the tree starting from the root and ending with the last token of the key. Function f is fold over values associated with all substrings of the key, starting from a zero substring.

val remove : 'a t -> key -> unit

remove trie key removes value bound with key if any.

val longest_match : 'a t -> key -> (int * 'a) option

longest_match trie k find the value associated with a longest substring of a key k. Returns a pair - a length of matched key and data, associated with that key.

val length : 'a t -> int

length trie returns the amount of entries in the trie

val pp : 'a Regular.Std.printer -> 'a t Regular.Std.printer

pp pp_val creates a printer for a given value printer pp_val. Example:

let int_trie = String.Trie.pp pp_int

will create a printer for a String.Trie that is populated by integers.

OCaml

Innovation. Community. Security.

GitHub Discord Twitter Peertube RSS
About
Changelog Releases Industrial Users Academic Users Why OCaml
Ecosystem
Packages Community Events OCaml Planet Jobs
Resources
Install OCaml Get Started Platform Tools Language Manual Standard Library API Books Exercises Papers OCaml Playground Logo
Policies
Carbon Footprint Governance Privacy Code of Conduct