# AstWalker.java

    /*
    ** Module   : AstWalker.java
    ** Abstract : Walks AST hierarchies and applies rulesets to them
    **
    ** Copyright (c) 2005-2017, Golden Code Development Corporation.
    **
    ** -#- -I- --Date-- --JPRM-- ----------------------------Description-----------------------------
    ** 001 ECF 20050301   @20137 Created initial version. Traverses an AST and
    **                           applies all walk-rules from a ruleset against
    **                           each node.
    ** 002 ECF 20050303   @20158 Fixed defect in iterator method. When walking
    **                           a subset of the tree from a non-root node
    **                           using a limited depth, siblings of the top
    **                           node were being mistakenly included.
    ** 003 ECF 20050303   @20162 Moved the underlying implementation of the
    **                           iterator method into uast.AnnotatedAst. The
    **                           method here now delegates to that method.
    ** 004 ECF 20050316   @20413 Add support for descent/ascent rules. These
    **                           are applied as we transition through nesting
    **                           levels during AST traversal. Removed obsolete
    **                           iterator method.
    ** 005 ECF 20050428   @20922 Added nextChild method. Notifies of a lateral
    **                           transition from a left sibling to its next,
    **                           right sibling. The parent AST is passed as a
    **                           parameter. This mimics recursive behavior.
    ** 006 GES 20050613   @21474 Added next child index support.
    ** 007 GES 20050728   @21897 Added support for the honor-hidden attribute
    **                           of the rule-set. When enabled, non-root
    **                           AST nodes that are accessed will drop from
    **                           the walk if their hidden flag is set.
    ** 008 ECF 20050811   @22087 Added support for read-only mode. When in
    **                           read-only mode, the AST symbol resolver is
    **                           configured with the source AST for both its
    **                           source and copy AST (i.e., there is no copy).
    ** 009 ECF 20050819   @22176 Added support for premature walk termination.
    **                           At each iteration of the walk loop, a flag in
    **                           the symbol resolver is checked to determine
    **                           if the next node should be visited. If not,
    **                           the loop is terminated.
    ** 010 ECF 20060221   @24707 Added try-catch around AST iteration. Reports
    **                           source AST in the event of an expression
    **                           exception by wrapping the exception in
    **                           another, with an augmented error message.
    ** 011 GES 20090429   @42072 Import change.
    ** 012 GES 20090518   @42385 Import change.
    ** 013 ECF 20140403          Implemented generics.
    ** 014 ECF 20150715          Replace StringBuffer with StringBuilder.
    ** 015 ECF 20171228          Improve performance by reducing context-local lookups.
    */
    /*
    ** This program is free software: you can redistribute it and/or modify
    ** it under the terms of the GNU Affero General Public License as
    ** published by the Free Software Foundation, either version 3 of the
    ** License, or (at your option) any later version.
    **
    ** This program is distributed in the hope that it will be useful,
    ** but WITHOUT ANY WARRANTY; without even the implied warranty of
    ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
    ** GNU Affero General Public License for more details.
    **
    ** You may find a copy of the GNU Affero GPL version 3 at the following
    ** location: https://www.gnu.org/licenses/agpl-3.0.en.html
    **
    ** Additional terms under GNU Affero GPL version 3 section 7:
    **
    **   Under Section 7 of the GNU Affero GPL version 3, the following additional
    **   terms apply to the works covered under the License.  These additional terms
    **   are non-permissive additional terms allowed under Section 7 of the GNU
    **   Affero GPL version 3 and may not be removed by you.
    **
    **   0. Attribution Requirement.
    **
    **     You must preserve all legal notices or author attributions in the covered
    **     work or Appropriate Legal Notices displayed by works containing the covered
    **     work.  You may not remove from the covered work any author or developer
    **     credit already included within the covered work.
    **
    **   1. No License To Use Trademarks.
    **
    **     This license does not grant any license or rights to use the trademarks
    **     Golden Code, FWD, any Golden Code or FWD logo, or any other trademarks
    **     of Golden Code Development Corporation. You are not authorized to use the
    **     name Golden Code, FWD, or the names of any author or contributor, for
    **     publicity purposes without written authorization.
    **
    **   2. No Misrepresentation of Affiliation.
    **
    **     You may not represent yourself as Golden Code Development Corporation or FWD.
    **
    **     You may not represent yourself for publicity purposes as associated with
    **     Golden Code Development Corporation, FWD, or any author or contributor to
    **     the covered work, without written authorization.
    **
    **   3. No Misrepresentation of Source or Origin.
    **
    **     You may not represent the covered work as solely your work.  All modified
    **     versions of the covered work must be marked in a reasonable way to make it
    **     clear that the modified work is not originating from Golden Code Development
    **     Corporation or FWD.  All modified versions must contain the notices of
    **     attribution required in this license.
    */

    package com.goldencode.p2j.pattern;

    import java.util.*;
    import com.goldencode.ast.*;
    import com.goldencode.expr.*;

    /**
     * Traverses an AST hierarchy or an arbitrary iteration of AST nodes, and
     * applies a set of rules against each source-copy AST node pair encountered
     * during the walk. The traversal is always defined by the <b>source</b> AST.
     * That is, nodes visited while walking are always nodes from the source AST.
     * As each node is visited, an {@link AstSymbolResolver} is updated to refer
     * to that source node, as well as to a companion <b>copy</b> node. The
     * companion copy node is retrieved using the source node's ID, from a map
     * which is provided at construction.
     * <p>
     * By convention, rules which modify AST nodes must operate only on copy
     * AST nodes. Most rules which test state without making modifications
     * operate on source AST nodes.
     * <p>
     * Instances of this class are used by the pattern engine to apply a pipeline
     * of rulesets to a hierarchy of AST nodes.
     *
     * @see  PatternEngine
     * @see  AstSymbolResolver
     * @see  RuleSet
     */
    public class AstWalker
    implements AstWalkListener
    {
       /** The set of rules associated with this AST walker */
       private RuleSet ruleSet = null;

       /** Map of AST copy nodes, indexed by source AST IDs */
       private Map<Long, Aast> copies = null;

       /** Object used resolve AST-related expression symbols */
       private AstSymbolResolver resolver = null;

       /**
        * Constructor which accepts a ruleset and a map of AST copy nodes,
        * which are initially identical copies of source AST nodes.
        *
        * @param   ruleSet
        *          Ruleset which will be applied against the AST walked by this
        *          walker.
        * @param   copies
        *          Map of writable AST (copy) nodes, indexed by the IDs of the
        *          source AST nodes which they mirror.
        */
       public AstWalker(RuleSet ruleSet, Map<Long, Aast> copies)
       {
          this.ruleSet = ruleSet;
          this.copies = copies;
       }

       /**
        * Fully walk the specified AST from root to every leaf, applying our
        * ruleset's walk-rules to each source-copy node combination encountered
        * in the walk.
        *
        * @param   resolver
        *          Symbol resolver used to resolve variables and user functions
        *          for the logical expressions within the rules contained in the
        *          ruleset.
        * @param   ast
        *          Root node of the AST hierarchy to be walked. Note that this
        *          need not be the absolute root of the entire tree, but can be
        *          any node in the tree. May not be <code>null</code>.
        *
        * @return  An object which iterates over the filtered list of results
        *          (if any) from the application of this ruleset.
        *
        * @see     AstSymbolResolver#view
        */
       public Iterator<Aast> walk(AstSymbolResolver resolver, Aast ast)
       {
          return walk(resolver, ast, 0);
       }

       /**
        * Walk the specified AST from root to a maximum node depth of
        * <code>maxLevels</code>, applying our ruleset's walk-rules to each
        * source-copy node combination encountered in the walk.
        *
        * @param   resolver
        *          Symbol resolver used to resolve variables and user functions
        *          for the logical expressions within the rules contained in the
        *          ruleset.
        * @param   ast
        *          Root node of the AST hierarchy to be walked. Note that this
        *          need not be the absolute root of the entire tree, but can be
        *          any node in the tree. May not be <code>null</code>.
        * @param   maxLevels
        *          Maximum number of levels or generations to visit relative to
        *          the root defined by <code>ast</code>. If the tree contains
        *          more levels than <code>maxLevels</code>, the levels beyond a
        *          relative depth of <code>maxLevels</code> will be ignored. Set
        *          to <code>0</code> to disable this restriction.
        *
        * @return  An object which iterates over the filtered list of results
        *          (if any) from the application of this ruleset.
        *
        * @see     AstSymbolResolver#view
        */
       public Iterator<Aast> walk(AstSymbolResolver resolver, Aast ast, int maxLevels)
       {
          return walk(resolver, ast.iterator(maxLevels, this, ruleSet.isHonorHidden()));
       }

       /**
        * Traverse the specified iterator, applying our ruleset's walk-rules to
        * each source-copy node combination encountered in the walk. At each
        * node, the resolver's state is updated with references to the current
        * source and copy AST node. Because the copy AST node is retrieved
        * from a map based on the ID of the source node, a non-<code>null</code>
        * copy node is guaranteed to be provided to the resolver at each stop.
        * However, the copy node <em>is not</em> guaranteed to have a valid
        * state, nor to be located in the same relative location within its
        * containing hierarchy as its companion source node, nor even reside in
        * the tree at all. This is because previous rules may have changed its
        * state or removed it entirely from the tree.
        * <p>
        * As the tree is traversed, the ruleset's ascent and descent rules, if
        * any, are applied each time the walk ascends to a parent node level or
        * descends to a child node level, respectively. The respective rules are
        * applied once per level traversed, even if an ascent moves from a deeply
        * nested node back up to a sibling node of an ancestor several levels up.
        * Note that the AST in the resolver's scope at the time descent rules are
        * applied will always be the first child of the new level (descents
        * always occur only one level at a time). However, on ascent, the AST in
        * the resolver's scope will always be the <em>next AST to be visited</em>,
        * which will
        *
        * @param   resolver
        *          Symbol resolver used to resolve variables and user functions
        *          for the logical expressions within the rules contained in the
        *          ruleset.
        * @param   iter
        *          Iterator which defines which AST nodes will be visited during
        *          the traversal.
        *
        * @return  An object which iterates over the filtered list of results
        *          (if any) from the application of this ruleset.
        *
        * @see     AstSymbolResolver#view
        */
       public Iterator<Aast> walk(AstSymbolResolver resolver, Iterator<Aast> iter)
       {
          this.resolver = resolver;

          try
          {
             while (!resolver.isEndWalk() && iter.hasNext())
             {
                // Set the source and copy ASTs in the resolver.
                configureResolver((Aast) iter.next());

                // Apply walk rules (unconditionally).
                ruleSet.apply(resolver, RuleContainer.RULE_WALK);
             }
          }
          catch (ExpressionException exc)
          {
             Aast src = resolver.getSourceAst();
             StringBuilder buf = new StringBuilder(exc.getMessage());
             buf.append(" [");
             buf.append(src);
             buf.append(" id=");
             buf.append(src != null ? src.getId().toString() : "N/A");
             buf.append("]");

             throw new ExpressionException(buf.toString(), exc);
          }

          return resolver.view();
       }

       /**
        * Called whenever a transition from a child node to its parent takes
        * place during an AST walk. This will be called <em>before</em> the
        * next AST node in the tree traversal is visited.
        * <p>
        * This method first configures the AST symbol resolver by storing in it
        * the source and copy AST nodes which represent the <em>parent</em>
        * node in the child to parent transition. It then applies the ascent
        * rules, if any, configured for the current ruleset.
        *
        * @param   ast
        *          Source AST node which represents the parent in the child to
        *          parent transition of the current AST walk.
        */
       public void ascent(Aast ast)
       {
          configureResolver(ast);
          ruleSet.apply(resolver, RuleContainer.RULE_ASCENT);
       }

       /**
        * Called whenever a transition from a parent node to its first child
        * takes place during an AST walk. This will be called <em>before</em> the
        * next AST node in the tree traversal is visited.
        * <p>
        * This method first configures the AST symbol resolver by storing in it
        * the source and copy AST nodes which represent the <em>parent</em>
        * node in the parent to child transition. It then applies the descent
        * rules, if any, configured for the current ruleset.
        *
        * @param   ast
        *          Source AST node which represents the parent in the parent to
        *          child transition of the current AST walk.
        */
       public void descent(Aast ast)
       {
          configureResolver(ast);
          ruleSet.apply(resolver, RuleContainer.RULE_DESCENT);
       }

       /**
        * Called whenever a transition from a child node to its next right
        * sibling takes place during an AST walk. This will be called
        * <em>before</em> the next AST node in the tree traversal is visited.
        * The parent node of the children is in scope at the time of
        * notification. This effectively mimics recursion by notifying the
        * listener when one child node has been processed, before the next is
        * visited. This allows the listener to perform parent-level processing
        * between visits to child nodes.
        * <p>
        * This method is <em>not</em> invoked after the last child is visited,
        * as this is the purpose of the {@link #ascent} method.
        * <p>
        * This method first configures the AST symbol resolver by storing in it
        * the source and copy AST nodes which represent the <em>parent</em>
        * node of the children between which the lateral transition is taking
        * place. It then applies the next-child rules, if any, configured for
        * the current ruleset.
        *
        * @param   ast
        *          Source AST node which represents the parent of the children
        *          between which the lateral transition is taking place in the
        *          current AST walk.
        * @param   index
        *          The 0-based index of the child which is about to be processed.
        */
       public void nextChild(Aast ast, int index)
       {
          configureResolver(ast);
          resolver.setNextChildIndex(index);
          ruleSet.apply(resolver, RuleContainer.RULE_NEXT_CHILD);
          resolver.setNextChildIndex(-1);
       }

       /**
        * Configure the AST symbol resolver by storing in it the specified AST
        * as its current source AST and the associated copy AST as its current
        * copy AST. This is required to allow rules to have a source and
        * copy AST in the symbol resolver's context when the rules condition
        * and action expressions are evaluated.
        *
        * @param   ast
        *          Source tree AST node to be set into the symbol resolver.
        */
       private void configureResolver(Aast ast)
       {
          Aast copy = ast;
          if (copies != null && !copies.isEmpty())
          {
             copy = (Aast) copies.get(ast.getId());
          }

          resolver.setAsts(ast, copy);
       }
    }