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);
}
}