Module Traversable.HelpersSource

Utility functions for building traversals.

Parameters

Signature

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)

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)