/** * This module contains generic one-pass traversals over terms. * * These traversals have been defined using the primitive term traversal * operators of Stratego, all, some and one, and the control operators of * language. This results is a wide variety of resuable term traversals. * * Term traversals can be categorized into classes according to * how much of the term they traverse and to which parts * of the term they modify. Please read the annotated source code * to see the breakdown. * * @author Eelco Visser <visser@acm.org> * @author Martin Bravenboer <martin.bravenboer@gmail.com> * @author Karl Trygve Kalleberg <karltk@strategoxt.org> - documentation */ module strategy/traversal/simple imports strategy/conditional term/properties /** * Traverse a term everywhere. * * The most general class of traversals visits every node * of a term and applies a transformation to it. The following * operators define traversals that apply a strategy s * to all nodes of a term. */ strategies /** Apply strategy s to each term in a top down, left to right, * (prefix) order. * * Note: new terms resulting from rewrites during the traversal will * also be traversed. * * @param s - the strategy to apply * @type Term -> Term */ topdown(s) = s; all(topdown(s)) /** Apply strategy s to each term in a bottom up, left to right, * (postfix) order. * * @param s - the strategy to apply * @type Term -> Term */ bottomup(s) = all(bottomup(s)); s /** Apply strategy s to all terms going down then going up. The traversal * will traverse the spine until a leaf is reached, then proceed to the * other leaves, before it returns up the spine. * * Each term, including the leaves, will be visited in both the down and * up directions. * * @param s - the strategy to apply * @type Term -> Term */ downup(s) = s; all(downup(s)); s /** Apply strategy s1 to all terms going down then apply s2 to all terms * when going up. This strategy will traverse the spine until a leaf is * reached, then proceed to the other leaves until none are left, before * it returns up the spine. * * Each term, including the leaves, will be visited in both the down and * up directions, with s1 then s2 applied to it, respectively. * * @param s1 - the strategy applied on the way down * @param s2 - the strategy applied on the way up * @type Term -> Term * @see downup */ downup(s1, s2) = s1; all(downup(s1, s2)); s2 downup2(s1, s2) = s1; all(downup2(s1, s2)); s2 /** * Traversal that can stop at certain points. * * The traversals above go through all constructors. If it * is not necessary to traverse the entire tree, the following * versions of the traversals can be used. They are parameterized * with a strategy operator 'stop' that */ strategies /** Apply strategy s to each term in a top down, left to right, (prefix) * order, but stop traversal when stop succeeds. * * @param s Term -> Term * @param stop (a -> a) * a -> a * @type Term -> Term * @see topdown */ topdownS(s, stop: (a -> a) * a -> a) = s ; (stop(topdownS(s,stop)) <+ all(topdownS(s,stop))) /** Apply strategy s to each term in a bottom up, left to right, (postfix) * order, but stop traversal when stop succeeds. * * @param s Term -> Term * @param stop (a -> a) * a -> a * @type Term -> Term * @see bottomup */ bottomupS(s, stop: (a -> a) * a -> a) = (stop(bottomupS(s, stop)) <+ all(bottomupS(s, stop))) ; s /** Apply strategy s to all terms when going down then when going up, * but stop traversal when stop succeeds. * * @param s Term -> Term * @param stop (a -> a) * a -> a * @type Term -> Term * @see downup */ downupS(s, stop: (a -> a) * a -> a) = s ; (stop(downupS(s, stop)) <+ all(downupS(s, stop))); s /** Apply strategy s1 to all terms going down then apply s2 to all terms * when going up, but stop travesal when stop succeeds. * * @param s1 Term -> Term * @param s2 Term -> Term * @param stop (a -> a) * a -> a * @type Term -> Term * @see downup */ downupS(s1, s2, stop: (a -> a) * a -> a) = s1 ; (stop(downupS(s1, s2, stop)) <+ all(downupS(s1, s2, stop))) ; s2 /** * A unit for topdownS, bottomupS and downupS. For example, * topdown(s) is equivalent to topdownS(s,don't-stop). * * @param s Term -> Term * @type _ -> fail * @see topdownS * @see bottomupS * @see downupS */ don't-stop(s) = fail /** * A variation on bottomup is a traversal that also provides the * original term as well as the term in which the direct subterms * have been transformed. (also known as a paramorphism?) */ bottomup-para(s) = !(<id>, <all(bottomup-para(s))>) ; s /** * Traversal of a term along a spine. * * A spine of a term is a chain of nodes from the root to some * subterm. 'spinetd' goes down one spine and applies 's' along * the way to each node on the spine. The traversal stops when * 's' fails for all children of a node. */ strategies /** * Apply s along the spine of a term, in top down order. * * A spine of a term is a chain of nodes from the root to some * subterm. The traversal stops when 's' fails for all children * of a node. * * @param s Term -> Term * @type Term -> Term */ spinetd(s) = s; try(one(spinetd(s))) /** * Apply s along the spine of a term, in bottom up order. * * A spine of a term is a chain of nodes from the root to some * subterm. The traversal stops when 's' fails for all children * of a node. * * @param s Term -> Term * @type Term -> Term */ spinebu(s) = try(one(spinebu(s))); s spinetd'(s) = s; (one(spinetd'(s)) + all(fail)) spinebu'(s) = (one(spinebu'(s)) + all(fail)); s /** * Apply s everywhere along all spines where s applies. */ strategies /** Apply s everywhere along all spines where s applies, in top down * order. * * @param s Term -> Term * @type Term -> Term * @see spinetd */ somespinetd(s) = rec x(s; try(some(x))) /** Apply s everywhere along all spines where s applies, in bottom * up order. * * @param s Term -> Term * @type Term -> Term * @see spinetd */ somespinebu(s) = rec x(try(some(x)); s) /** * Apply s at one position. One s application has to succeed. */ strategies /** Apply s at one position inside a term, in top down order. Once * s has succeeded, the traversal stops. If s never succeeds, this * strategy fails. * * @param s Term -> Term * @type Term -> Term */ oncetd(s) = rec x(s <+ one(x)) /** Apply s at one position inside a term, in bottom up order. Once * s has succeeded, the traversal stops. If s never succeeds, this * strategy fails. * * @param s Term -> Term * @type Term -> Term */ oncebu(s) = rec x(one(x) <+ s) oncetd-skip(s, skip: (a -> a) * a -> a) = rec x(s <+ skip(x) <+ one(x)) /** * Apply s at some positions, but at least one. * * As soon as one is found, searching is stopped, i.e., in the top-down case * searching in subtrees is stopped, in bottom-up case, searching * in upper spine is stopped. */ strategies /** Apply s at some positions inside a term, at least once, in top * down order. Once s succeeds, the traversal stopped. * * @param s Term -> Term * @type Term -> Term * @see oncetd */ sometd(s) = rec x(s <+ some(x)) /** Apply s at some positions inside a term, at least once, in bottom * up order. Once s succeeds, the traversal stopped. * * @param s Term -> Term * @type Term -> Term * @see oncetd */ somebu(s) = rec x(some(x) <+ s) /** * Frontier * * Find all topmost applications of 's' */ strategies /** Find all topmost applications of s. * * @param s Term -> Term * @type Term -> Term */ alltd(s) = rec x(s <+ all(x)) alldownup2(s1, s2) = rec x((s1 <+ all(x)); s2) alltd-fold(s1, s2) = rec x(s1 <+ all(x); s2) /** * Leaves */ strategies leaves(s, is-leaf, skip: (a -> a) * a -> a) = rec x((is-leaf; s) <+ skip(x) <+ all(x)) leaves(s, is-leaf) = rec x((is-leaf; s) <+ all(x)) /** * Find as many applications as possible, but at least one. */ strategies /** Apply s as many times as possible, but at least once, in bottom up * order. * * @param s Term -> Term * @type Term -> Term */ manybu(s) = rec x(some(x); try(s) <+ s) /** Apply s as many times as possible, but at least once, in top down * order. * * @param s Term -> Term * @type Term -> Term */ manytd(s) = rec x(s; all(try(x)) <+ some(x)) strategies somedownup(s) = rec x(s; all(x); try(s) <+ some(x); try(s)) /** Apply s to a term in breadth first order. * * @param s Term -> Term * @type Term -> Term */ breadthfirst(s) = rec x(all(s); all(x))