/**
 * 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@cs.uu.nl> - 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))