package travesty

  1. Overview
  2. Docs
Legend:
Library
Module
Module type
Parameter
Class
Class type

Utility functions for building traversals.

Parameters

module M : Base.Monad.S

Signature

type 'a traversal = 'a -> 'a M.t

traversal is shorthand for a traversal function over M.

Variants

Functions beginning proc_variant are useful for building traversable containers on top of Variantslib's map function.

Here's an example where we define a generic traversal function over a variant type using proc_variant1 and proc_variant3, then use it to build a traversable container instance for inspecting and modifying a specific type of data regardless of variant.

(* This type describes x86 operands: *)
type t =
  | Location of Location.t
  | Immediate of Disp.t
  | String of string
  | Typ of string
  | Bop of t * operator * t [@@deriving variants]

(* We use the helpers to build an intermediate mapper... *)
module Base_map (M : Monad.S) = struct
  module F = Travesty.Traversable.Helpers (M)

  let rec map_m (x : t) ~location ~immediate ~string ~typ ~bop
    : t M.t =
    Variants.map x
      ~location:(F.proc_variant1 location)
      ~immediate:(F.proc_variant1 immediate)
      ~string:(F.proc_variant1 string)
      ~typ:(F.proc_variant1 typ)
      (* Note that this recursively folds down the operands,
         and that the [bop] function only receives the operator. *)
      ~bop:(F.proc_variant3 (fun (l, b, r) ->
          let open M.Let_syntax in
          let%bind l' = map_m ~location ~immediate ~string ~typ ~bop l in
          let%bind b' = bop b in
          let%map  r' = map_m ~location ~immediate ~string ~typ ~bop r in
          (l', b', r')))
  ;;
end

(* ...then use it to build a traversable container over all of
   the symbols in an operand. *)
module On_symbols
  : Travesty.Traversable.S0_container with type t := t
                                       and type elt := string =
  Travesty.Traversable.Make_container0 (struct
    type nonrec t = t
    module Elt = String

    module On_monad (M : Monad.S) = struct
      module B = Base_map (M)
      (* Recursively using other traversables: *)
      module L = Location.On_symbols.On_monad (M)
      module D = Disp.On_symbols.On_monad (M)

      let map_m t ~f =
        B.map_m t
          ~location:(L.map_m ~f)
          ~immediate:(D.map_m ~f)
          (* These don't contain symbols: *)
          ~string:M.return
          ~typ:M.return
          ~bop:M.return
    end
  end)
val proc_variant0 : Base.unit traversal -> 'cont Base.Variant.t -> 'cont M.t

proc_variant0 f variant lifts a traversal f over a Variantslib nullary variant constructor variant.

val proc_variant1 : 'a traversal -> ('a -> 'cont) Base.Variant.t -> 'a -> 'cont M.t

proc_variant1 f variant a lifts a traversal f over a Variantslib unary variant constructor variant with argument a.

val proc_variant2 : ('a * 'b) traversal -> ('a -> 'b -> 'cont) Base.Variant.t -> 'a -> 'b -> 'cont M.t

proc_variant2 f variant a b lifts a traversal f over a Variantslib binary variant constructor variant with arguments a and b.

val proc_variant3 : ('a * 'b * 'c) traversal -> ('a -> 'b -> 'c -> 'cont) Base.Variant.t -> 'a -> 'b -> 'c -> 'cont M.t

proc_variant3 f variant a b c lifts a traversal f over a Variantslib ternary variant constructor variant with arguments a, b, and c.

Fields

The function proc_field is useful for building traversable containers on top of Fieldslib's fold function.

Here's an example where we define a generic traversal function over a record type using proc_field, then use it to build a traversable container instance for inspecting and modifying a specific type of data inside the record.

(* Type for holding x86 memory references. *)
type t =
  { seg    : Reg.t   option (* segment register *)
  ; disp   : Disp.t  option (* displacement *)
  ; base   : Reg.t   option (* base register *)
  ; index  : Index.t option (* index *)
  } [@@deriving fields]

(* First, build a generic traversal function (this isn't,
   itself, a Traversable)... *)
module Base_map (M : Monad.S) = struct
  module F = Travesty.Traversable.Helpers (M)
  let map_m indirect ~seg ~disp ~base ~index =
    Fields.fold
      ~init:(M.return indirect)
      ~seg:(F.proc_field seg)
      ~disp:(F.proc_field disp)
      ~base:(F.proc_field base)
      ~index:(F.proc_field index)
end

(* Now, we can build a traversable container instance.
     This one extracts symbols from memory references. *)
module On_symbols
  : Travesty.Traversable.S0_container with type t := t
                                       and type elt := string =
  Travesty.Traversable.Make_container0 (struct
    type nonrec t = t
    module Elt = String
    module Set = String.Set

    module On_monad (M : Monad.S) = struct
      module B = Base_map (M)
      module D = Disp.On_symbols.On_monad (M)
      module O = My_option.On_monad (M)

      let map_m t ~f =
        B.map_m t
          (* Chained monadic traversal. *)
          ~disp:(O.map_m ~f:(D.map_m ~f))
          (* Segments, bases, and indices have no symbols. *)
          ~seg:M.return
          ~base:M.return
          ~index:M.return
    end
  end)
val proc_field : 'elt traversal -> 'cont M.t -> ([> `Set_and_create ], 'cont, 'elt) Base.Field.t_with_perm -> 'cont M.t

proc_field f state field container original lifts a traversal f to a form comparible with Fieldslib's fold function.

OCaml

Innovation. Community. Security.