AST Traversals

Writing Traverses

For each kind of traversal (described below), ppxlib provides a "default" traversal, in the form of a class following the visitors pattern. For instance, in the case of the map traversal, the default map is the identity AST map, and any object of class Ast_traverse.map will be this identity map. To apply a map to a node of a given type, one needs to call the appropriate method:

# let f payload =
    let map = new Ppxlib.Ast_traverse.map in
    map#payload ;;
val f : payload -> payload = <fun>

In the example above, f is the identity map. But we want to define proper maps, not just identity. This is done by creating a new class, making it inherit the methods, and replacing the one that we want to replace. Here is an example, for both the iter and map traversals:

let f payload =
  let checker =
    object
      inherit Ast_traverse.iter as super

      method! extension ext =
        match ext with
        | { txt = "forbidden"; _ }, _ ->
            failwith "Fordidden extension nodes are forbidden!"
        | _ -> super#extension ext (* Continue traversing inside the node *)
    end
  in
  let replace_constant =
    object
      inherit Ast_traverse.map
      method! int i = i + 1
    end
  in
  checker#payload payload;
  replace_constant#payload payload

Note that when redefining methods, unless explicitly wanting the traversal to stop, the original method needs to be called! That should be all that’s necessary to know and understand the API.

The Different Kinds of Traversals

ppxlib offers different kind of Parsetree traversals:

• Iterators, which will traverse the type, calling a function on each node for side effects.

• Maps, where the content is replaced. A map will transform a Parsetree into another Parsetree, replacing nodes following the map function.

• Folds, which will traverse the nodes, carrying a value (often called an accumulator) that will be updated on each node.

• Lifts, a transformation that turns a Parsetree value in one of another type by transforming it in a bottom-up manner. For instance, with a simple tree structure, the corresponding lift function would be:

let lift ~f = function
    Leaf a -> f.leaf a
  | Node(a,x,y) -> f.node a (lift ~f x) (lift ~f y)

• Combinations of the two traversals, such as Fold-maps and Lift-maps.

• Variants of the above traversal, such as Maps with context, where a context can be modified and passed down to child nodes during traversal. The context never goes up; it is only propagated down. It is used for instance to track opened module. To give a simple example, such a context could be the depth of the current node, as in the following implementation for the simple tree type:

let map_with_depth_context ~f ctxt = function
    Leaf a -> f.leaf ctxt a
  | Node(a,x,y) ->
      f.node ctxt a
        (map_with_depth_context (ctxt+1) ~f x)
        (map_with_depth_context (ctxt+1) ~f y)