< Destructing AST nodes
Good practices >

AST Traversals

The Parsetree is a very complex type. Other Ppxlib modules such as Metaquot, Ast_builder and Ast_pattern help in generating and matching values, but only when the overall structure of the code is known in advance.

For other use cases, such as extracting all identifiers, checking that a property is verified, or replacing all integer constants by something else, those modules cannot really help. All these examples relate with another kind of Parsetree manipulations known as traversals.

A traversal is a recursive function that will be called on a value, and recursively on all of its subvalues, combining the result in a certain way. For instance, List.map is a traversal of the list type. In the case of a list, a map is very simple to write, but in the case of the long Parsetree type, it is a lot of boilerplate code! Fortunately, ppxlib provides a way to ease this.

In ppxlib, traversals are implemented using the "visitor" object-oriented pattern.

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:

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

< Destructing AST nodes
Good practices >