mirror of
https://github.com/ocaml-tracing/ocaml-trace.git
synced 2026-03-08 20:07:55 -04:00
31 lines
7.6 KiB
HTML
31 lines
7.6 KiB
HTML
<!DOCTYPE html>
|
||
<html xmlns="http://www.w3.org/1999/xhtml"><head><title>ast-traversal (ppxlib.ast-traversal)</title><meta charset="utf-8"/><link rel="stylesheet" href="../_odoc-theme/odoc.css"/><meta name="generator" content="odoc 3.1.0"/><meta name="viewport" content="width=device-width,initial-scale=1.0"/><script src="../highlight.pack.js"></script><script>hljs.initHighlightingOnLoad();</script></head><body class="odoc"><nav class="odoc-nav"><a href="index.html">Up</a> – <a href="../index.html">Index</a> » <a href="index.html">ppxlib</a> » ast-traversal</nav><header class="odoc-preamble"><p> <div style="display: flex; justify-content:space-between"><div><a href="matching-code.html" title="matching-code">< Destructing AST nodes</a> </div><div><a href="good-practices.html" title="good-practices">Good practices ></a> </div></div></p><h1 id="ast-traversals"><a href="#ast-traversals" class="anchor"></a>AST Traversals</h1><p>The <a href="Astlib/Ast_502/Parsetree/index.html" title="Ppxlib.Parsetree"><code>Parsetree</code></a> is a very complex type. Other <a href="Ppxlib/index.html"><code>Ppxlib</code></a> modules such as <a href="Ppxlib_metaquot/index.html" title="Ppxlib_metaquot"><code>Metaquot</code></a>, <a href="Ppxlib/Ast_builder/index.html" title="Ppxlib.Ast_builder"><code>Ast_builder</code></a> and <a href="Ppxlib/Ast_pattern/index.html" title="Ppxlib.Ast_pattern"><code>Ast_pattern</code></a> help in generating and matching values, but only when the overall structure of the code is known in advance.</p><p>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 <a href="Astlib/Ast_502/Parsetree/index.html" title="Ppxlib.Parsetree"><code>Parsetree</code></a> manipulations known as traversals.</p><p>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, <a href="../ocaml/Stdlib/List/index.html#val-map" title="Stdlib.List.map"><code>List.map</code></a> is a traversal of the <code>list</code> type. In the case of a <code>list</code>, a map is very simple to write, but in the case of the long <a href="Astlib/Ast_502/Parsetree/index.html" title="Ppxlib.Parsetree"><code>Parsetree</code></a> type, it is a lot of boilerplate code! Fortunately, <a href="Ppxlib/index.html" title="Ppxlib"><code>ppxlib</code></a> provides a way to ease this.</p><p>In <code>ppxlib</code>, traversals are implemented using the "visitor" object-oriented pattern.</p></header><div class="odoc-tocs"><nav class="odoc-toc odoc-local-toc"><ul><li><a href="#writing-traverses">Writing Traverses</a></li><li><a href="#the-different-kinds-of-traversals">The Different Kinds of Traversals</a></li></ul></nav></div><div class="odoc-content"><h2 id="writing-traverses"><a href="#writing-traverses" class="anchor"></a>Writing Traverses</h2><p>For each kind of traversal (described below), <code>ppxlib</code> 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 <a href="Ppxlib/Ast_traverse/class-map/index.html" title="Ppxlib.Ast_traverse.map"><code>Ast_traverse.map</code></a> will be this identity map. To apply a map to a node of a given type, one needs to call the appropriate method:</p><pre class="language-ocaml"><code> # let f payload =
|
||
let map = new Ppxlib.Ast_traverse.map in
|
||
map#payload ;;
|
||
val f : payload -> payload = <fun></code></pre><p>In the example above, <code>f</code> 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 <code>iter</code> and <code>map</code> traversals:</p><pre class="language-ocaml"><code>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</code></pre><p>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 <a href="Ppxlib/Ast_traverse/class-map/index.html" title="Ppxlib.Ast_traverse.map">API</a>.</p><h2 id="the-different-kinds-of-traversals"><a href="#the-different-kinds-of-traversals" class="anchor"></a>The Different Kinds of Traversals</h2><p><a href="Ppxlib/index.html" title="Ppxlib"><code>ppxlib</code></a> offers different kind of <a href="Astlib/Ast_502/Parsetree/index.html" title="Ppxlib.Parsetree"><code>Parsetree</code></a> traversals:</p><ul><li><a href="Ppxlib/Ast_traverse/class-iter/index.html" title="Ppxlib.Ast_traverse.iter">Iterators</a>, which will traverse the type, calling a function on each node for side effects.</li></ul><ul><li><a href="Ppxlib/Ast_traverse/class-map/index.html" title="Ppxlib.Ast_traverse.map">Maps</a>, where the content is replaced. A map will transform a <code>Parsetree</code> into another <code>Parsetree</code>, replacing nodes following the map function.</li></ul><ul><li><a href="Ppxlib/Ast_traverse/class-fold/index.html" title="Ppxlib.Ast_traverse.fold">Folds</a>, which will traverse the nodes, carrying a value (often called an accumulator) that will be updated on each node.</li></ul><ul><li><a href="Ppxlib/Ast_traverse/class-lift/index.html" title="Ppxlib.Ast_traverse.lift">Lifts</a>, a transformation that turns a <code>Parsetree</code> value in one of another type by transforming it in a bottom-up manner. For instance, with a simple tree structure, the corresponding <code>lift</code> function would be:</li></ul><pre class="language-ocaml"><code> let lift ~f = function
|
||
Leaf a -> f.leaf a
|
||
| Node(a,x,y) -> f.node a (lift ~f x) (lift ~f y)</code></pre><ul><li>Combinations of the two traversals, such as <a href="Ppxlib/Ast_traverse/class-fold_map/index.html" title="Ppxlib.Ast_traverse.fold_map">Fold-maps</a> and <a href="Ppxlib/Ast_traverse/class-lift_map_with_context/index.html" title="Ppxlib.Ast_traverse.lift_map_with_context">Lift-maps</a>.</li></ul><ul><li>Variants of the above traversal, such as <a href="Ppxlib/Ast_traverse/class-map_with_context/index.html" title="Ppxlib.Ast_traverse.map_with_context">Maps with context</a>, 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:</li></ul><pre class="language-ocaml"><code> 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)</code></pre><p> <div style="display: flex; justify-content:space-between"><div><a href="matching-code.html" title="matching-code">< Destructing AST nodes</a> </div><div><a href="good-practices.html" title="good-practices">Good practices ></a> </div></div></p></div></body></html>
|