/* Implementation of a recursive algorithm to match a pattern to any subgraph of
a graph.
@Copyright (c) 2007-2014 The Regents of the University of California.
All rights reserved.
Permission is hereby granted, without written agreement and without
license or royalty fees, to use, copy, modify, and distribute this
software and its documentation for any purpose, provided that the
above copyright notice and the following two paragraphs appear in all
copies of this software.
IN NO EVENT SHALL THE UNIVERSITY OF CALIFORNIA BE LIABLE TO ANY PARTY
FOR DIRECT, INDIRECT, SPECIAL, INCIDENTAL, OR CONSEQUENTIAL DAMAGES
ARISING OUT OF THE USE OF THIS SOFTWARE AND ITS DOCUMENTATION, EVEN IF
THE UNIVERSITY OF CALIFORNIA HAS BEEN ADVISED OF THE POSSIBILITY OF
SUCH DAMAGE.
THE UNIVERSITY OF CALIFORNIA SPECIFICALLY DISCLAIMS ANY WARRANTIES,
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. THE SOFTWARE
PROVIDED HEREUNDER IS ON AN "AS IS" BASIS, AND THE UNIVERSITY OF
CALIFORNIA HAS NO OBLIGATION TO PROVIDE MAINTENANCE, SUPPORT, UPDATES,
ENHANCEMENTS, OR MODIFICATIONS.
PT_COPYRIGHT_VERSION_2
COPYRIGHTENDKEY
*/
package ptolemy.actor.gt;
import java.io.File;
import java.util.Collection;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Set;
import ptolemy.actor.CompositeActor;
import ptolemy.actor.Director;
import ptolemy.actor.IOPort;
import ptolemy.actor.TypedIOPort;
import ptolemy.actor.gt.data.FastLinkedList;
import ptolemy.actor.gt.data.MatchResult;
import ptolemy.actor.gt.data.SequentialTwoWayHashMap;
import ptolemy.actor.gt.data.Tuple;
import ptolemy.actor.gt.ingredients.criteria.Criterion;
import ptolemy.data.BooleanToken;
import ptolemy.data.Token;
import ptolemy.data.expr.Parameter;
import ptolemy.data.type.Type;
import ptolemy.kernel.ComponentEntity;
import ptolemy.kernel.CompositeEntity;
import ptolemy.kernel.Port;
import ptolemy.kernel.Relation;
import ptolemy.kernel.util.Attribute;
import ptolemy.kernel.util.IllegalActionException;
import ptolemy.kernel.util.KernelRuntimeException;
import ptolemy.kernel.util.NamedObj;
import ptolemy.moml.MoMLParser;
import ptolemy.util.StringUtilities;
/**
Implementation of a recursive algorithm to match a pattern to any subgraph of a
a graph. The pattern is specified as the pattern part of a graph
transformation rule. The graph to be matched to, called host graph, is
an arbitrary Ptolemy II model, whose top level is an instance of {@link
CompositeEntity}.
@author Thomas Huining Feng
@version $Id: GraphMatcher.java 70402 2014-10-23 00:52:20Z cxh $
@since Ptolemy II 7.1
@Pt.ProposedRating Yellow (tfeng)
@Pt.AcceptedRating Red (tfeng)
*/
public class GraphMatcher extends GraphAnalyzer {
///////////////////////////////////////////////////////////////////
//// public methods ////
/** Return the most recent match result, which the user should not modify.
* During the matching process, when a callback routine (an instance
* implementing {@link MatchCallback}) is invoked (see {@link
* #setMatchCallback(MatchCallback)}), that callback routine can call this
* method to retrieve the match result that has just been found.
*
* Note that the returned match result object may be changed by future
* matching. To maintain a copy, {@link MatchResult#clone()} may be called
* that returns a clone of it.
*
* @return The most recent match result.
*/
public MatchResult getMatchResult() {
return _matchResult;
};
/** Return whether the last matching was successful.
*
* @return Whether the last matching was successful.
*/
public boolean isSuccessful() {
return _success;
}
/** Match a rule file to a model file. This main method takes a parameter
* array of length 2 or 3. If the array's length is 2, the first string is
* the rule file name, and the second is the model file name. In this case,
* an arbitrary match (the first one found) is printed to the console. If
* the array has 3 elements, the first string should be "-A"
* (meaning "all matches"), the second string is the rule file name, and
* the third is the model file name. In that case, all the matches are
* printed to to console one by one.
*
* @param args The parameter array.
* @exception Exception If the rule file or the model file cannot be read.
*/
public static void main(String[] args) throws Exception {
if (!(args.length == 2 || args.length == 3
&& args[0].equalsIgnoreCase("-A"))) {
System.err.println("USAGE: java [-A] "
+ GraphMatcher.class.getName() + " ");
StringUtilities.exit(1);
}
final boolean all = args.length == 3 && args[0].equalsIgnoreCase("-A");
String ruleXMLFile = all ? args[1] : args[0];
String hostXMLFile = all ? args[2] : args[1];
MatchCallback matchCallback = new MatchCallback() {
@Override
public boolean foundMatch(GraphMatcher matcher) {
MatchResult match = matcher.getMatchResult();
System.out.println("--- Match " + ++count + " ---");
_printMatch(match);
return !all;
}
private int count = 0;
};
match(ruleXMLFile, hostXMLFile, matchCallback);
}
/** Match a pattern specified in the patternGraph to a model in
* hostGraph. If the match is successful, true is
* returned, and the match result is stored internally, which can be
* retrieved with {@link #getMatchResult()}. A matching was successful if
* at least one match result was found, and the callback (an instance
* implementing {@link MatchCallback}) returned true when it was
* invoked.
*
* @param pattern The pattern.
* @param hostGraph The host graph.
* @return true if the match is successful; false otherwise.
*/
public boolean match(Pattern pattern, CompositeEntity hostGraph) {
// Matching result.
_matchResult = new MatchResult(_parameterValues);
// Temporary data structures.
_parameterValues.clear();
_lookbackList.clear();
_temporaryMatch.clear();
_ignoredOptionalObjects.clear();
_callbacksInPattern.clear();
_clearCaches();
// Record the values of all the iterators.
Hashtable records = new Hashtable();
try {
GTTools.saveValues(pattern, records);
} catch (IllegalActionException e) {
throw new KernelRuntimeException(e, "Unable to save values.");
}
// Initially, we are not checking negated objects.
_negation = false;
_success = false;
_findAllMatchCallbacksInPattern(pattern);
try {
_success = _matchCompositeEntityAtAllLevels(pattern, hostGraph);
} finally {
_parameterValues.clear();
_ignoredOptionalObjects.clear();
_callbacksInPattern.clear();
_clearCaches();
}
// Restore the values of all the iterators.
try {
GTTools.restoreValues(pattern, records);
} catch (IllegalActionException e) {
throw new KernelRuntimeException(e, "Unable to restore values.");
}
assert _lookbackList.isEmpty();
assert _temporaryMatch.isEmpty();
if (!_success) {
assert _matchResult.isEmpty();
}
return _success;
}
/** Match the rule stored in the file with name ruleXMLFile to the
* model stored in the file with name hostXMLFile, whose top-level
* should be an instance of {@link CompositeEntity}. The first match result
* (which is arbitrarily decided by the recursive algorithm) is recorded in
* the returned matcher object. This result can be obtained with {@link
* #getMatchResult()}. If the match is unsuccessful, the match result is
* empty, and {@link #isSuccessful()} of the returned matcher object
* returns false.
*
* @param ruleXMLFile The name of the file in which the rule is stored.
* @param hostXMLFile The name of the file in which the model to be matched
* is stored.
* @return A matcher object with the first match result stored in it. If no
* match is found, {@link #isSuccessful()} of the matcher object returns
* false, and {@link #getMatchResult()} returns an empty match.
* @exception Exception If the rule file or the model file cannot be read.
* @see #match(String, String, MatchCallback)
*/
public static GraphMatcher match(String ruleXMLFile, String hostXMLFile)
throws Exception {
return match(ruleXMLFile, hostXMLFile, null);
}
/** Match the rule stored in the file with name ruleXMLFile to the
* model stored in the file with name hostXMLFile, whose top-level
* should be an instance of {@link CompositeEntity}, and invoke
* callback's {@link MatchCallback#foundMatch(GraphMatcher)}
* method whenever a match is found. If the callback returns true,
* the match will terminate and no more matches will be reported;
* otherwise, the match process continues, and the callback may be invoked
* again. If callback is null, the behavior is the same
* as {@link #match(String, String)}.
*
* @param ruleXMLFile The name of the file in which the rule is stored.
* @param hostXMLFile The name of the file in which the model to be matched
* is stored.
* @param callback The callback to be invoked when matches are found.
* @return A matcher object with the last match result stored in it. If no
* match is found, or though matches are found, the callback returns
* false for all the matches, then {@link #isSuccessful()} of the
* matcher object returns false, and {@link #getMatchResult()}
* returns an empty match.
* @exception Exception If the rule file or the model file cannot be read.
* @see #match(String, String)
*/
public static GraphMatcher match(String ruleXMLFile, String hostXMLFile,
MatchCallback callback) throws Exception {
MoMLParser parser = new MoMLParser();
TransformationRule rule = (TransformationRule) parser.parse(null,
new File(ruleXMLFile).toURI().toURL());
parser.reset();
CompositeEntity host = (CompositeEntity) parser.parse(null, new File(
hostXMLFile).toURI().toURL());
GraphMatcher matcher = new GraphMatcher();
if (callback != null) {
matcher.setMatchCallback(callback);
}
matcher.match(rule.getPattern(), host);
return matcher;
}
/** Set the callback to be invoked by future calls to {@link
* #match(Pattern, CompositeEntity)}.
*
* @param callback The callback. If it is null, the callback is
* set to {@link #DEFAULT_CALLBACK}.
* @see #match(Pattern, CompositeEntity)
*/
public void setMatchCallback(MatchCallback callback) {
if (callback == null) {
_callback = DEFAULT_CALLBACK;
} else {
_callback = callback;
}
}
/** The default callback that always returns true. A callback is
* invoked whenever a match is found. Because this callback always returns
* true, it terminates the matching process after the first match
* is found, and the match result can be obtained later using {@link
* #getMatchResult()}.
*/
public static final MatchCallback DEFAULT_CALLBACK = new MatchCallback() {
@Override
public boolean foundMatch(GraphMatcher matcher) {
return true;
}
};
///////////////////////////////////////////////////////////////////
//// protected methods ////
/** Return whether the object in the pattern should be ignored in the
* pattern matching. An object is ignored if it is tagged to be ignored, or
* it is tagged to be optional but a match including that object has
* failed.
*
* @param object The object to be tested.
* @return true if the object is ignored.
*/
@Override
protected boolean _isIgnored(Object object) {
Boolean ignored = _cachedIgnoredObjects.get(object);
if (ignored != null) {
return ignored.booleanValue();
}
boolean result;
if (_isCreated(object) || GTTools.isIgnored(object)) {
result = true;
} else if (object instanceof NamedObj) {
NamedObj optionalContainer = _getOptionalContainer((NamedObj) object);
result = optionalContainer != null
&& _ignoredOptionalObjects.containsKey(optionalContainer)
&& _ignoredOptionalObjects.get(optionalContainer);
} else {
result = false;
}
_cachedIgnoredObjects.put(object, result);
return result;
}
/** Test whether the composite entity is opaque or not. Return true
* if the composite entity is an instance of {@link CompositeActor} and it
* is opaque. A composite actor is opaque if it has a director inside,
* which means the new level of hierarchy that it creates cannot be
* flattened, or it has a {@link HierarchyFlatteningAttribute} attribute
* inside with value true.
*
* @param entity The composite entity to be tested.
* @return true if the composite entity is an instance of {@link
* CompositeActor} and it is opaque.
*/
@Override
protected boolean _isOpaque(CompositeEntity entity) {
if (entity instanceof CompositeActor
&& ((CompositeActor) entity).isOpaque()) {
return true;
} else {
NamedObj container = entity.getContainer();
Token hierarchyFlatteningToken = _getAttribute(container,
HierarchyFlatteningAttribute.class, true, false, true);
boolean hierarchyFlattening = hierarchyFlatteningToken == null ? HierarchyFlatteningAttribute.DEFAULT
: ((BooleanToken) hierarchyFlatteningToken).booleanValue();
Token containerIgnoringToken = _getAttribute(container,
ContainerIgnoringAttribute.class, false, true, false);
boolean containerIgnoring = containerIgnoringToken == null ? ContainerIgnoringAttribute.DEFAULT
: ((BooleanToken) containerIgnoringToken).booleanValue();
return !hierarchyFlattening && !containerIgnoring;
}
}
/** Return whether the interconnected relations should be collapsed into one
* in pattern matching.
*
* @param container The container of the relations.
* @return true if the relation should be collapsed.
*/
@Override
protected boolean _relationCollapsing(NamedObj container) {
Token collapsingToken = _getAttribute(container,
RelationCollapsingAttribute.class, true, false, false);
if (collapsingToken == null) {
return RelationCollapsingAttribute.DEFAULT;
} else {
return ((BooleanToken) collapsingToken).booleanValue();
}
}
///////////////////////////////////////////////////////////////////
//// private methods ////
/** Check the items in the lookback list for more matching requirements. If
* no more requirements are found (i.e., all the lists in the lookback list
* have been fully explored), then a match is found, and the callback's
* {@link MatchCallback#foundMatch(GraphMatcher)} is invoked. If that
* method returns true, the matching process terminates; otherwise, the
* matching proceeds by backtracking.
*
* @return Whether the match is successful.
*/
private boolean _checkBackward() {
FastLinkedList.Entry entry = _lookbackList.getTail();
LookbackEntry lists = null;
while (entry != null) {
lists = entry.getElement();
if (!_negation && !lists.isFinished() || _negation
&& !lists.isNegated()) {
break;
}
entry = entry.getPrevious();
}
if (entry == null) {
if (_negation) {
return true;
} else {
_negation = true;
int matchSize = _matchResult.size();
if (_checkBackward() && _matchResult.size() > matchSize) {
_negation = false;
_matchResult.retain(matchSize);
return false;
} else {
_negation = false;
}
}
if (_checkConstraints()) {
for (MatchCallback callback : _callbacksInPattern) {
if (!callback.foundMatch(this)) {
return false;
}
}
return _callback.foundMatch(this);
} else {
return false;
}
} else {
return _matchList(lists);
}
}
/** Check whether the constraint is satisfied by the matching.
*
* @param pattern The object in the pattern that has been matched with the
* matched result stored in the _matchResult field.
* @param constraint The constraint to be checked.
* @return true if the constraint is satisfied.
*/
private boolean _checkConstraint(Pattern pattern, Constraint constraint) {
return constraint.check(pattern, _matchResult);
}
/** Check all the constraints are satisfied.
*
* @return true if all the constraints are satisfied.
*/
private boolean _checkConstraints() {
if (_matchResult.isEmpty()) {
return false;
}
Iterator> iterator = _matchResult.entrySet()
.iterator();
Map.Entry