| /******************************************************************************* |
| * 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;
|
|
|
| import org.eclipse.viatra2.gtasm.interpreter.exception.ViatraTransformationException; |
| import org.eclipse.viatra2.gtasm.patternmatcher.ExecutionMode; |
| import org.eclipse.viatra2.gtasm.patternmatcher.IMatching; |
| import org.eclipse.viatra2.gtasm.patternmatcher.ParameterMode; |
| import org.eclipse.viatra2.gtasm.patternmatcher.PatternCallSignature; |
| import org.eclipse.viatra2.gtasm.patternmatcher.Scope; |
| 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.callgraph.PatternNode; |
| 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.term.ITermHandler; |
| import org.eclipse.viatra2.gtasm.patternmatcher.patterns.IPatternMatcher; |
| import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.asm.enums.ContainmentMode;
|
| import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.asm.enums.ValueKind;
|
| import org.eclipse.viatra2.gtasmmodel.gtasm.metamodel.gt.GTPattern;
|
| import org.eclipse.viatra2.core.IEntity;
|
| import org.eclipse.viatra2.core.IModelElement;
|
| import org.eclipse.viatra2.core.IModelManager;
|
| import org.eclipse.viatra2.logger.Logger;
|
|
|
| import java.util.Arrays;
|
| import java.util.Collection;
|
| import java.util.HashMap;
|
| import java.util.Iterator;
|
| import java.util.Map;
|
| import java.util.Vector;
|
|
|
|
|
|
|
| /**
|
| * PatternMatcher is the (executable) run-time equivalent
|
| * of a GTPattern.
|
| *
|
| * The whole pattern matching engine is not represented as a single object, but
|
| * the container ASM interpreter module should consist of a set of
|
| * PatternMatcher objects.
|
| *
|
| * PatternMatcher objects (including all its subordinate data structures)
|
| * are generated by PatternBuilders.
|
| *
|
| * @author Gergely Varro, Akos Horvath
|
| */
|
| public class PatternMatcher implements IPatternMatcher {
|
| protected Logger logger;
|
| protected IModelManager manager;
|
| protected ITermHandler termHandler;
|
| protected PatternNode root;
|
| protected Map<String,Map<String,RemoteGoal>> rggMapping;
|
| |
| public PatternMatcher( Logger logger, IModelManager manager, ITermHandler termHandler) |
| throws PatternMatcherCompileTimeException { |
| this.logger = logger; |
| this.manager = manager; |
| this.termHandler = termHandler; |
| } |
|
|
| public PatternMatcher(GTPattern pattern, Logger logger, IModelManager manager, ITermHandler termHandler)
|
| throws PatternMatcherCompileTimeException {
|
| this.logger = logger;
|
| this.manager = manager;
|
| this.termHandler = termHandler;
|
| this.root = new PatternNode(this, pattern);
|
| this.rggMapping = new HashMap<String, Map<String,RemoteGoal>>();
|
| }
|
|
|
| public boolean match(Object[] inputMapping) throws ViatraTransformationException {
|
| PatternCallSignature[] signature =
|
| new PatternCallSignature[inputMapping.length];
|
| for (int i = 0; i < inputMapping.length; i++) {
|
| signature[i] = new PatternCallSignature();
|
| signature[i].setExecutionMode(ExecutionMode.SINGLE_RESULT);
|
|
|
| if (inputMapping[i] == null || inputMapping[i].equals(ValueKind.UNDEF_LITERAL)) {
|
| signature[i].setParameterMode(ParameterMode.OUTPUT);
|
| } else {
|
| signature[i].setParameterMode(ParameterMode.INPUT);
|
| }
|
| Scope scope = new Scope(Scope.DEFAULT_MODE, manager.getRoot());
|
| signature[i].setParameterScope(scope);
|
| }
|
| return (match(inputMapping, signature) != null);
|
| }
|
|
|
| public IMatching match(Object[] inputMapping,
|
| PatternCallSignature[] signature) throws ViatraTransformationException {
|
| for (int i = 0; i < signature.length; i++) {
|
| if (signature[i].getExecutionMode() == ExecutionMode.MULTIPLE_RESULTS) {
|
| String[] context = {root.getPattern().getName()}; |
| throw new PatternMatcherRuntimeException( |
| PatternMatcherErrorStrings.INTERNAL_PATTERNCALL_CHOOSE_WITH_MULTIPLERESULT |
| ,context |
| ,root.getPattern()); |
| //logger.warning("The method match(Object[], PatternCallSignature[] has been invoked in MULTIPLE_RESULTS execution mode.");
|
| //return null;
|
| }
|
| }
|
| Integer[] quantificationOrder = new Integer[signature.length];
|
| for (int i = 0; i < quantificationOrder.length; i++) {
|
| quantificationOrder[i] = i;
|
| }
|
| Collection<IMatching> solutions =
|
| matchAll(inputMapping, signature, quantificationOrder);
|
| for (IMatching matching : solutions) {
|
| return (MatchingFrame) matching;
|
| }
|
| return null;
|
| }
|
|
|
| /* public MatchingFrame matchFuture(Object[] inputMapping,
|
| PatternCallSignature[] signature) {
|
| try {
|
| // Initialization (IN/BELOW constraint processing)
|
| final Boolean[] adornment = new Boolean[signature.length];
|
| Vector<Object> vec = new Vector<Object>();
|
| Vector<Integer> freeVariables = new Vector<Integer>();
|
| int strongestConstraint = 0;
|
| int smallestWeight = 0;
|
| Scope s = signature[0].getParameterScope();
|
| if (s.getContainmentMode() == ContainmentMode.IN) {
|
| smallestWeight = ((IEntity) s.getParent()).getContents().size();
|
| } else if (s.getContainmentMode() == ContainmentMode.BELOW) {
|
| smallestWeight = ((IEntity) s.getParent()).getAllComponents().size();
|
| }
|
|
|
| for (int i = 0; i < signature.length; i++) {
|
| s = signature[i].getParameterScope();
|
| if (signature[i].getParameterMode() == ParameterMode.INPUT) {
|
| adornment[i] = true;
|
| vec.add(inputMapping[i]);
|
| if (s.getContainmentMode() == ContainmentMode.IN &&
|
| !((IEntity) s.getParent()).getContents().contains(inputMapping[i]) ||
|
| s.getContainmentMode() == ContainmentMode.BELOW &&
|
| !((IEntity) s.getParent()).getAllComponents().contains(inputMapping[i])) {
|
| logger.warning(FAILING_CONTAINMENT_CONSTRAINT);
|
| return null;
|
| }
|
| } else {
|
| adornment[i] = false;
|
| freeVariables.add(i);
|
| }
|
| if (s.getContainmentMode() == ContainmentMode.IN) {
|
| if (smallestWeight > ((IEntity) s.getParent()).getContents().size()) {
|
| smallestWeight = ((IEntity) s.getParent()).getContents().size();
|
| strongestConstraint = i;
|
| }
|
| } else if (s.getContainmentMode() == ContainmentMode.BELOW) {
|
| if (smallestWeight > ((IEntity) s.getParent()).getAllComponents().size()) {
|
| smallestWeight = ((IEntity) s.getParent()).getAllComponents().size();
|
| strongestConstraint = i;
|
| }
|
| }
|
| }
|
| adornment[strongestConstraint] = (freeVariables.size() == signature.length
|
| ? true : adornment[strongestConstraint]);
|
|
|
| // Preparing rule/goal graphs
|
| Map<String, RemoteGoal> rggRoots = new HashMap<String, RemoteGoal>();
|
| RemoteGoal main = root.buildRuleGoalGraph(adornment,rggRoots);
|
|
|
| // Magic set initialization
|
| if (freeVariables.size() == signature.length) {
|
| s = signature[strongestConstraint].getParameterScope();
|
| Iterator<IModelElement> i = (s.getContainmentMode() == ContainmentMode.IN
|
| ? ((IEntity) s.getParent()).getContents().iterator()
|
| : ((IEntity) s.getParent()).getAllComponents().iterator());
|
| for (; i.hasNext();) {
|
| Object[] input = new Object[1];
|
| input[0] = i.next();
|
| main.getMagicSet().addArray(new MatchingKey(input));
|
| }
|
| } else {
|
| Object[] input = new Object[vec.size()];
|
| vec.toArray(input);
|
| main.getMagicSet().addArray(new MatchingKey(input));
|
| }
|
|
|
| // Initial rule/goal graph synchronization
|
| boolean isModified = false;
|
| for (RemoteGoal goal : rggRoots.values()) {
|
| isModified = isModified || goal.synchronize();
|
| }
|
|
|
| // Pattern matching
|
| /*
|
| while (isModified) {
|
| isModified = false;
|
| // Calculation phase
|
| for (MatchingFrame frame = null; (frame = main.match(signature, freeVariables)) != null; ) {
|
| return frame;
|
| }
|
| for (RemoteGoal goal : rggRoots.values()) {
|
| if (!goal.equals(main)) {
|
| goal.matchAll();
|
| }
|
| }
|
| // Synchronization phase
|
| for (RemoteGoal goal : rggRoots.values()) {
|
| isModified = (goal.synchronize() ? true : isModified);
|
| }
|
| }
|
|
|
| } catch (PatternMatcherRuntimeException e) {}
|
| return null;
|
| }*/
|
|
|
| public Collection<IMatching> matchAll(Object[] inputMapping,
|
| PatternCallSignature[] signature,
|
| Integer[] quantificationOrder) throws ViatraTransformationException {
|
| try {
|
| // Key generator preparation based on the variables with forall quantifier
|
| if (signature.length != quantificationOrder.length) |
| {
|
| String[] context = {root.getPattern().getName()}; |
| throw new PatternMatcherRuntimeException( |
| PatternMatcherErrorStrings.INTERNAL_QUANTIFICATION_AND_SIGNATURES_PARAMETER_MISMATCH |
| ,context |
| ,root.getPattern());
|
| }
|
| int multipleUpperBound = 0;
|
| Vector<Integer> vector = new Vector<Integer>();
|
| for (int i = 0; i < quantificationOrder.length; i++) {
|
| Integer index = quantificationOrder[i];
|
| if (index < signature.length) {
|
| if (signature[index].getExecutionMode() == ExecutionMode.MULTIPLE_RESULTS) {
|
| if (i <= multipleUpperBound) {
|
| vector.add(index);
|
| multipleUpperBound++;
|
| } else {
|
| String[] context = {root.getPattern().getName()}; |
| throw new PatternMatcherRuntimeException( |
| PatternMatcherErrorStrings.INTERNAL_QUANTIFICATION_ORDER |
| ,context |
| ,root.getPattern());
|
| }
|
| }
|
| } else {
|
| String[] context = {root.getPattern().getName()}; |
| throw new PatternMatcherRuntimeException( |
| PatternMatcherErrorStrings.INTERNAL_QUANTIFICATION_ORDER |
| ,context |
| ,root.getPattern());
|
| }
|
| }
|
| final Integer[] keys = new Integer[vector.size()];
|
| vector.toArray(keys);
|
| IKeyGenerator<MatchingKey, MatchingFrame> resultKeyGenerator =
|
| new IKeyGenerator<MatchingKey, MatchingFrame>() {
|
|
|
| public MatchingKey calculateKey(MatchingFrame value) {
|
| Object[] matchingKey = new Object[keys.length];
|
| for (int i = 0; i < keys.length; i++) {
|
| matchingKey[i] = value.getValue(keys[i]);
|
| }
|
| return new MatchingKey(matchingKey);
|
| }
|
|
|
| public int size() {
|
| return keys.length;
|
| }
|
| };
|
|
|
| // Matching table initalization
|
| MatchingTable result = new MatchingTable();
|
| if (signature.length == 0) {
|
| return result;
|
| }
|
|
|
| // Initialization (IN/BELOW constraint processing)
|
| final Boolean[] adornment = new Boolean[signature.length];
|
| Vector<Object> vec = new Vector<Object>();
|
| for (int i = 0; i < signature.length; i++) {
|
| if (signature[i].getParameterMode() == ParameterMode.INPUT) {
|
| adornment[i] = true;
|
| vec.add(inputMapping[i]);
|
| } else {
|
| adornment[i] = false;
|
| }
|
| }
|
|
|
| int strongestConstraint = 0;
|
| if (vec.size() == 0) {
|
| int largestDistance = 0;
|
| boolean hasInConstraint = false;
|
| for (int i = 0; i < signature.length; i++) {
|
| Scope s = signature[i].getParameterScope();
|
| int distance = 0;
|
| IEntity parent = (IEntity) s.getParent();
|
| for (distance = 0; !parent.equals(manager.getRoot()); distance++) {
|
| parent = parent.getParent();
|
| }
|
|
|
| if (s.getContainmentMode() == ContainmentMode.IN) {
|
| if (hasInConstraint && distance > largestDistance) {
|
| largestDistance = distance;
|
| strongestConstraint = i;
|
| } else if (!hasInConstraint) {
|
| hasInConstraint = true;
|
| largestDistance = distance;
|
| strongestConstraint = i;
|
| }
|
| } else if (s.getContainmentMode() == ContainmentMode.BELOW) {
|
| if (!hasInConstraint && distance > largestDistance) {
|
| largestDistance = distance;
|
| strongestConstraint = i;
|
| }
|
| }
|
| }
|
| adornment[strongestConstraint] = true;
|
| }
|
|
|
| // Preparing rule/goal graphs
|
| String adornmentString = Arrays.deepToString(adornment);
|
| Map<String, RemoteGoal> rggRoots = rggMapping.get(adornmentString);
|
| if (rggRoots == null) {
|
| rggRoots = new HashMap<String, RemoteGoal>();
|
| root.buildRuleGoalGraph(adornment,rggRoots);
|
| rggMapping.put(adornmentString, rggRoots);
|
| }
|
| RemoteGoal main = rggRoots.get(RemoteGoal.generateID(root, adornment));
|
|
|
| // Magic set initialization
|
| if (vec.size() == 0) {
|
| MagicSet ms = main.getMagicSet();
|
| Scope s = signature[strongestConstraint].getParameterScope();
|
| IEntity parent = (IEntity) s.getParent();
|
| Iterator<IModelElement> i = (s.getContainmentMode() == ContainmentMode.IN
|
| ? parent.getElementsInNamespace().iterator()
|
| : parent.getAllElementsInNamespace().iterator());
|
| for (; i.hasNext();) {
|
| Object[] input = new Object[1];
|
| input[0] = i.next();
|
| ms.addArray(new MatchingKey(input));
|
| }
|
| } else {
|
| Object[] input = new Object[vec.size()];
|
| vec.toArray(input);
|
| main.getMagicSet().addArray(new MatchingKey(input));
|
| }
|
|
|
| // Initial rule/goal graph synchronization
|
| boolean isModified = false;
|
| for (RemoteGoal goal : rggRoots.values()) {
|
| isModified = (goal.synchronize() ? true : isModified);
|
| }
|
|
|
| // Pattern matching
|
| while (isModified) {
|
| isModified = false;
|
| // Calculation phase
|
| for (RemoteGoal goal : rggRoots.values()) {
|
| goal.matchAll();
|
| }
|
| // Synchronization phase
|
| for (RemoteGoal goal : rggRoots.values()) {
|
| isModified = (goal.synchronize() ? true : isModified);
|
| }
|
| }
|
| |
| //for debug purposes |
| //System.out.println("**********Final DEBUG*********"); |
| //for (RemoteGoal goal : rggRoots.values()) { |
| // goal.debug(); |
| //} |
| |
|
|
| // Postprocessing (filling the matching table)
|
| for (MatchingFrame frame : main) {
|
| boolean constraintsFulfilled = true;
|
| // Checking IN/BELOW constraints on the result
|
| for (int i = 0; constraintsFulfilled && i < signature.length; i++) {
|
| if (signature[i].getParameterMode() == ParameterMode.OUTPUT) {
|
| Scope s = signature[i].getParameterScope();
|
| IEntity container = (IEntity) s.getParent();
|
| Object obj = frame.getValue(i);
|
| if (obj instanceof IModelElement) {
|
| IModelElement me = (IModelElement) obj;
|
| if (s.getContainmentMode() == ContainmentMode.IN) {
|
| constraintsFulfilled = me.getNamespace().compareTo(container) == 0;
|
| } else if (s.getContainmentMode() == ContainmentMode.BELOW) {
|
| constraintsFulfilled = me.isBelowNamespace(container);
|
| }
|
| } else {
|
| // TODO gervarro: what happens, if a formal parameter is a String, integer and it has a container constraint?
|
| }
|
| }
|
| }
|
| if (constraintsFulfilled) {
|
| // If all constraints are fulfilled, add the frame to the matching table
|
| result.put(resultKeyGenerator.calculateKey(frame), frame);
|
| }
|
| }
|
| // Clean up for all runtime data structures (except for the result)
|
| for (RemoteGoal rg : rggRoots.values()) {
|
| rg.init();
|
| }
|
| return result;
|
| } catch (PatternMatcherRuntimeException e) {
|
| throw e.addNewStackElement(root.getPattern());
|
| }
|
| }
|
| public IMatching matchRandomly(Object[] inputMapping, |
| PatternCallSignature[] signature) throws ViatraTransformationException { |
| Integer[] quantificationOrder = new Integer[inputMapping.length]; |
| for (int i=0; i<quantificationOrder.length; i++) quantificationOrder[i] = i; |
| Collection<IMatching> allMatches = matchAll(inputMapping, signature, quantificationOrder); |
| if (allMatches == null || allMatches.isEmpty()) return null; |
| else return (IMatching) allMatches.toArray()[(int)(Math.random() * allMatches.size())]; |
| // TODO suboptimal |
| } |
|
|
| /**
|
| *
|
| * @return the logger
|
| */
|
| public Logger getLogger() {
|
| return logger;
|
| }
|
|
|
| /**
|
| * @return the termHandler
|
| */
|
| public ITermHandler getTermHandler() {
|
| return termHandler;
|
| }
|
|
|
| public IModelManager getModelManager() {
|
| return manager;
|
| } |
| |
|
|
| }
|
