| /******************************************************************************* |
| * Copyright (c) 2004-2008 Akos Horvath, Gergely Varro and Daniel Varro |
| * All rights reserved. This program and the accompanying materials |
| * are made available under the terms of the Eclipse Public License v1.0 |
| * which accompanies this distribution, and is available at |
| * http://www.eclipse.org/legal/epl-v10.html |
| * |
| * Contributors: |
| * Akos Horvath, Gergely Varro - initial API and implementation |
| *******************************************************************************/ |
| |
| package org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.callgraph;
|
|
|
| import org.eclipse.viatra2.core.IModelManager;
|
| import org.eclipse.viatra2.gtasm.patternmatcher.PatternCallSignature; |
| import org.eclipse.viatra2.gtasm.patternmatcher.exceptions.PatternMatcherCompileTimeException; |
| import org.eclipse.viatra2.gtasm.patternmatcher.exceptions.PatternMatcherRuntimeException; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.MatchingFrame; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.PatternMatcherErrorStrings; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.SearchPlan; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.SearchPlanKey; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.VariableID; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.algorithms.ISearchGraph; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.algorithms.SearchGraphFactory; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.operation.DummyOperation; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.operation.InjectivityCheckOperation; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.operation.PatternCallOperation; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.operation.SearchPlanOperation; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.rgg.IQueueContentProvider; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.rgg.IndexedRule; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.rgg.LocalGoal; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.rgg.MagicSet; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.rgg.RemoteGoal; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.rgg.UnindexedRule; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.internal.searchgraph.AbstractNode; |
| import org.eclipse.viatra2.gtasm.patternmatcher.impl.patternmatcher.term.ITermHandler; |
| import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.asm.core.AnnotatedElement; |
| import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.asm.core.GTASMElement; |
| import org.eclipse.viatra2.logger.Logger;
|
|
|
| import java.util.ArrayList; |
| import java.util.Collection;
|
| import java.util.HashMap;
|
| import java.util.HashSet;
|
| import java.util.List;
|
| import java.util.Map;
|
| import java.util.Set;
|
| import java.util.SortedSet;
|
| import java.util.TreeMap;
|
| import java.util.TreeSet;
|
| import java.util.Vector;
|
|
|
|
|
| /**
|
| * A FlattenedPattern corresponds to a PatternBody, in which
|
| * variables from all the embedded pattern invocations are aggregated.
|
| *
|
| * FlattenedPatterns are generated during the pattern invocation analysis of
|
| * GTPatternBodies. If the pattern call graph is a DAG, then we have a
|
| * non-recursive FlattenedPattern consisting of all the variables that appear
|
| * in the GTPatternBody itself or any patterns that are called by the
|
| * GTPatternBody.
|
| *
|
| * Each branch of OR patterns obviously generate a new FlattenedPattern.
|
| *
|
| * The interpreted engine uses the following mapping:
|
| * VariableType => PatternVariable
|
| */
|
| public class FlattenedPattern extends EvenLevelNode
|
| implements Comparable<FlattenedPattern> {
|
|
|
| private boolean isRecursionBased;
|
|
|
| private ISearchGraph searchGraph;
|
| /**
|
| * The mapping of pattern variables to their location in
|
| * the PatternFrames.
|
| */
|
| private Map<VariableID,Integer> variableMapping;
|
| private Map<Integer, Set<VariableID>> inverseVariableMapping;
|
|
|
| private Set<Pair> injectivityExclusionSet, injectivityInclusionSet;
|
|
|
| /**
|
| * The mapping of PatternSignatures to the SearchPlans
|
| * that are available for a given PatternSignature.
|
| */
|
| private Map<SearchPlanKey,Collection<SearchPlan>> searchPlanMapping;
|
|
|
| private Vector<SearchPlanOperation> preSearchPlanOperations;
|
| private Vector<SearchPlanOperation> postSearchPlanOperations;
|
|
|
| /**
|
| * The size of the binding arrays inside the corresponding
|
| * MatchingFrames.
|
| */
|
| private int frameSize;
|
| private int injectivityFrameSize;
|
|
|
| public FlattenedPattern(PatternNode parent, List<IFlattenedPatternElement> specification)
|
| throws PatternMatcherCompileTimeException {
|
| super(parent);
|
| //this.SearchGraph = new VPMBasedSearchGraph(parent.getModelManager());
|
| this.searchGraph = SearchGraphFactory.getSearchGraph(parent.getModelManager());
|
| this.variableMapping = new HashMap<VariableID, Integer>();
|
| this.inverseVariableMapping = new TreeMap<Integer, Set<VariableID>>();
|
| this.searchPlanMapping = new HashMap<SearchPlanKey, Collection<SearchPlan>>();
|
| this.preSearchPlanOperations = new Vector<SearchPlanOperation>();
|
| this.postSearchPlanOperations = new Vector<SearchPlanOperation>();
|
| this.isRecursionBased = false;
|
| this.frameSize = 0;
|
| this.injectivityFrameSize = 0;
|
| this.injectivityExclusionSet = new HashSet<Pair>(); |
| injectivityInclusionSet = new HashSet<Pair>();
|
|
|
| Logger logger = parent.getLogger();
|
| // Main loop for processing all the variables of a pattern variant
|
| for (int i = 0; i < specification.size(); i++) {
|
| IFlattenedPatternElement element = specification.get(i);
|
| element.setCurrentLocation(i);
|
| element.addFormalParameters(this);
|
| element.addLocalVariables(this);
|
| }
|
| injectivityFrameSize = frameSize;
|
| for (int i = 0; i < specification.size(); i++) {
|
| IFlattenedPatternElement element = specification.get(i);
|
| element.processNegativeApplicationConditions(this, logger, parent.getModelManager());
|
| element.processCheckExpressions(this, logger);
|
| element.buildSearchGraph(this);
|
| element.generateElementInjectivityConstraints(this, |
| element.processVariableAssignments(this), |
| element.processInjectivityAssignments(this)); |
|
|
| // element.processFormalParameterScopes(this);
|
| //Scope of the input parameter is not added to the search graph
|
| // element.processPatternCallScopes(this);
|
| }
|
| this.searchGraph.connectDanglingRelations(this);
|
| addPostSearchPlanOperation(new InjectivityCheckOperation());
|
|
|
| //TODO: in case of adaptive pattern matching the searchNodeOrder is not fix have to go back to the iSearchGraph itself
|
| // the order of the nodes are calculated, it would be better to have it contained
|
| |
| //For debugging purpose
|
| // result.searchNodeOrder= result.alg.evaulateSearchPlan(result);
|
| // result.debug();
|
| // //result.debugPL(a);
|
| // result.alg.evaulateOperationPlan(result.searchNodeOrder);
|
|
|
| printVariableMapping(logger);
|
| }
|
|
|
| /**
|
| * Adds SearchPlan plan to the set of search plans with
|
| * PatternSignature signature.
|
| * @param signature The key that identifies the set of search plans
|
| * to which plan has to be added.
|
| * @param plan The search plan to be added.
|
| * @return true if plan has been successfully added to the
|
| * search plan mapping dictionary.
|
| */
|
| boolean addSearchPlan(PatternCallSignature signature, SearchPlan plan) {
|
| return false;
|
| }
|
|
|
| MatchingFrame getInstance() {
|
| return null;
|
| }
|
|
|
| Collection<SearchPlan> getSearchPlansFor(SearchPlanKey key) {
|
| return searchPlanMapping.get(key);
|
| }
|
|
|
| /**
|
| *
|
| * @return the frameSize
|
| */
|
| public int getFrameSize() {
|
| return frameSize;
|
| }
|
|
|
| /**
|
| * @param frameSize the frameSize to set
|
| */
|
| public void setFrameSize(int frameSize) {
|
| this.frameSize = frameSize;
|
| }
|
|
|
| public ISearchGraph getSearchGraph() {
|
| return searchGraph;
|
| }
|
|
|
| public void addPreSearchPlanOperation(SearchPlanOperation operation) {
|
| preSearchPlanOperations.add(operation);
|
| }
|
|
|
| public void addPostSearchPlanOperation(SearchPlanOperation operation) {
|
| postSearchPlanOperations.add(operation);
|
| }
|
|
|
| public Integer getIndex(VariableID variable) {
|
| return variableMapping.get(variable);
|
| }
|
|
|
| public Set<VariableID> getVariableIDs(Integer index) {
|
| return inverseVariableMapping.get(index);
|
| }
|
|
|
| private void addToInverseMapping(VariableID variable, Integer index) {
|
| Set<VariableID> idSet = inverseVariableMapping.get(index);
|
| if (idSet == null) {
|
| idSet = new HashSet<VariableID>();
|
| inverseVariableMapping.put(index, idSet);
|
| }
|
| idSet.add(variable);
|
| }
|
|
|
| public void setIndex(VariableID variable, Integer index) {
|
| variableMapping.put(variable, index);
|
| addToInverseMapping(variable, index);
|
| }
|
|
|
| public int addVariable(VariableID variable) {
|
| if (variable != null) {
|
| variableMapping.put(variable, frameSize);
|
| addToInverseMapping(variable, frameSize);
|
| }
|
| return frameSize++;
|
| }
|
|
|
| private void printVariableMapping(Logger logger) {
|
| for (VariableID id : variableMapping.keySet()) {
|
| logger.debug(id.toString() + " : " + variableMapping.get(id));
|
| }
|
| for (Integer key : inverseVariableMapping.keySet()) {
|
| for (VariableID id : inverseVariableMapping.get(key)) {
|
| logger.debug(key + " : " + id.toString());
|
| }
|
| }
|
| logger.debug("Injective frame size: \t" + injectivityFrameSize);
|
| logger.debug("Frame size: \t" + frameSize);
|
| }
|
|
|
| public boolean containsIndex(VariableID variable){
|
| return variableMapping.containsKey(variable);
|
| }
|
|
|
| // Moves non-recursion based patterns ahead of recursion based patterns
|
| public int compareTo(FlattenedPattern o) {
|
| /*
|
| * this = o : !isRecursionBased AND !o.isRecursionBased
|
| * this = o : isRecursionBased AND o.isRecursionBased
|
| * this > o : isRecursionBased AND !o.isRecursionBased
|
| * this < o : !isRecursionBased AND o.isRecursionBased
|
| */
|
| if (isRecursionBased == o.isRecursionBased) {
|
| return 0;
|
| } else {
|
| return (isRecursionBased ? 1 : -1);
|
| }
|
| }
|
|
|
| /**
|
| * @return the injectivityFrameSize
|
| */
|
| public int getInjectivityFrameSize() {
|
| return injectivityFrameSize;
|
| }
|
|
|
| public ITermHandler getTermHandler() {
|
| return parent.getTermHandler();
|
| }
|
|
|
| public Collection<SearchPlanOperation> generateCoreSearchPlan(Boolean[] adornment, IModelManager manager) throws PatternMatcherRuntimeException{
|
| return searchGraph.generateSearchPlan(this, adornment, manager);
|
| }
|
|
|
| public List<SearchPlanOperation> generateSearchPlan(Boolean[] adornment, IModelManager manager) throws PatternMatcherRuntimeException{
|
| Collection<SearchPlanOperation> vec = searchGraph.generateSearchPlan(this, adornment,manager);
|
|
|
| // Copies pre and post operations
|
| ArrayList<SearchPlanOperation> finalSearchPlan = new ArrayList<SearchPlanOperation>();
|
| finalSearchPlan.addAll(preSearchPlanOperations);
|
| finalSearchPlan.addAll(vec);
|
| finalSearchPlan.addAll(postSearchPlanOperations);
|
| SearchPlanOperation[] operations = new SearchPlanOperation[finalSearchPlan.size()];
|
| operations = finalSearchPlan.toArray(operations);
|
| SearchPlan splan = new SearchPlan(operations);
|
| splan.printDebugInformation(parent.getLogger());
|
| // sets the iSearchGraph back to starting state
|
| searchGraph.initSearchGraph();
|
|
|
| return finalSearchPlan;
|
| }
|
|
|
| IQueueContentProvider buildSubtree(Map<String, RemoteGoal> rggRoots,
|
| MagicSet ms,
|
| List<SearchPlanOperation> searchPlan,
|
| int upperBound,
|
| SortedSet<Integer> preCallInterfaceVariables) throws PatternMatcherRuntimeException {
|
| //gervarro: put to the constructor of the Rule?
|
| SortedSet<Integer> localVariables = new TreeSet<Integer>();
|
| int i = upperBound;
|
| for (; i >= 0 && !(searchPlan.get(i) instanceof PatternCallOperation); i--) {
|
| searchPlan.get(i).calculateSidewaysPassedVariables(preCallInterfaceVariables);
|
| searchPlan.get(i).calculateLocalVariables(localVariables);
|
| }
|
|
|
| if (upperBound < 0) {
|
| // sup_i.0 :- ms_i
|
| return ms; // look up the appropriate magic set
|
| } else if (i < upperBound) {
|
| // sup_i.j :- sup_i.(j-1), local_j
|
| IQueueContentProvider left =
|
| buildSubtree(rggRoots, ms, searchPlan, i, preCallInterfaceVariables);
|
| List<SearchPlanOperation> operations =
|
| new Vector<SearchPlanOperation>(searchPlan.subList(i+1, upperBound+1));
|
| operations.add(new DummyOperation());
|
| SearchPlanOperation[] array = new SearchPlanOperation[operations.size()];
|
| array = operations.toArray(array);
|
| LocalGoal right = new LocalGoal(array);
|
|
|
| /*
|
| int size = localVariables.size();
|
| Integer[] localVariableMapping = new Integer[size];
|
| Boolean[] adornment = new Boolean[size];
|
| int counter = 0;
|
| for (Integer position: localVariables) {
|
| adornment[counter] = preCallInterfaceVariables.contains(position);
|
| counter++;
|
| }
|
| localVariables.toArray(localVariableMapping);
|
| */
|
|
|
| return new UnindexedRule(this, left, right);
|
| } else if (i == upperBound) {
|
| // sup_i.j :- sup_i.(j-1), remote_j
|
| PatternCallOperation pco = (PatternCallOperation) searchPlan.get(i);
|
| pco.calculateSidewaysPassedVariables(preCallInterfaceVariables);
|
| pco.calculateLocalVariables(localVariables);
|
|
|
| IQueueContentProvider left =
|
| buildSubtree(rggRoots, ms, searchPlan, i-1, preCallInterfaceVariables);
|
|
|
| String id = RemoteGoal.generateID(pco.getPatternNode(), pco.getAdornment());
|
| // If right goal exists in runtimes
|
| if (rggRoots.containsKey(id)) {
|
| // then get the runtime from runtimes
|
| RemoteGoal right = rggRoots.get(id);
|
| return new IndexedRule(this, left, right, pco.getParameterMapping(), pco.getAdornment());
|
| } else {
|
| // else generate a new runtime
|
| RemoteGoal right = pco.getPatternNode().buildRuleGoalGraph(pco.getAdornment(),rggRoots);
|
| return new IndexedRule(this, left, right, pco.getParameterMapping(), pco.getAdornment());
|
| }
|
| // ms_call :- sup_i.(j-1)
|
| // Explicitly handled by RemoteGoal
|
| } else { |
| String[] context = {getParent().getPattern().getName()};
|
| throw new PatternMatcherRuntimeException( |
| PatternMatcherErrorStrings.INTERNAL_FLATTENED_PATTERN_BUILD |
| ,context |
| ,getParent().getPattern());
|
| }
|
| } |
| |
| public AnnotatedElement getGTASMRepresentation(AbstractNode node){ |
| return searchGraph.getGTASMRepresentation(node); |
| } |
| |
| |
|
|
|
|
| public Pair addInjectivityExclusionPair(int left, int right) {
|
| Pair p = (left < right ? new Pair(left,right) : new Pair(right,left));
|
| injectivityExclusionSet.add(p); |
| return p;
|
| } |
| |
| public void removeInjectivityExclusionPair(int left, int right) { |
| Pair p = (left < right ? new Pair(left,right) : new Pair(right,left)); |
| injectivityExclusionSet.remove(p); |
| }
|
| |
| public Pair addInjectivityInclusionPair(int left, int right) { |
| Pair p = (left < right ? new Pair(left,right) : new Pair(right,left)); |
| injectivityInclusionSet.add(p); |
| return p; |
| } |
| |
| public void removeInjectivityInclusionPair(int left, int right) { |
| Pair p = (left < right ? new Pair(left,right) : new Pair(right,left)); |
| injectivityInclusionSet.remove(p); |
| |
| } |
|
|
| public boolean isIncludedInInjectivityCheck(int i, int j) {
|
| Pair p = (i < j ? new Pair(i,j) : new Pair(j,i));
|
| return injectivityInclusionSet.contains(p); // if it is in the Inclusion set then it has to be checked for injectivity (|| !injectivityExclusionSet.contains(p))
|
| }
|
|
|
| public static class Pair {
|
| public Integer getLeft() { |
| return left; |
| } |
| |
| public Integer getRight() { |
| return right; |
| } |
| |
| private Integer left;
|
| private Integer right;
|
|
|
| Pair(int left, int right) {
|
| this.left = left;
|
| this.right = right;
|
| }
|
|
|
| public boolean equals(Object other) {
|
| if (other != null && other instanceof Pair) {
|
| Pair o = (Pair) other;
|
| return (left == o.left && right == o.right);
|
| } else {
|
| return false;
|
| }
|
| }
|
|
|
| public int hashCode() {
|
| return left.hashCode() + right.hashCode();
|
| }
|
| } |
| |
| |
| |
|
|
| }
|
