[441323] First prototype for binary transitive closure extend

This change introduces a naive extend impementation for binary
transitive closure, and also replaces deducible constraint checking for
single-use checking.

A revisiting of cost functions is still necessary, but that will not be
included in this change.

Change-Id: I50fefcdf7dcddcac08d49eeb16dddcf71eb9d5b8
Signed-off-by: Zoltan Ujhelyi <ujhelyiz@incquerylabs.com>

5 files changed, 211 insertions, 15 deletions

diff --git a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/check/BinaryTransitiveClosureCheck.java b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/check/BinaryTransitiveClosureCheck.java
index 25709e4ce..61af5605a 100644
--- a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/check/BinaryTransitiveClosureCheck.java
+++ b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/check/BinaryTransitiveClosureCheck.java
@@ -10,7 +10,10 @@
  *******************************************************************************/
 package org.eclipse.viatra.query.runtime.localsearch.operations.check;
 
+import java.util.HashSet;
+import java.util.LinkedList;
 import java.util.List;
+import java.util.Queue;
 import java.util.Set;
 
 import org.eclipse.viatra.query.runtime.localsearch.MatchingFrame;
@@ -23,7 +26,6 @@ import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
 
 import com.google.common.collect.ImmutableMap;
 import com.google.common.collect.Lists;
-import com.google.common.collect.Sets;
 
 /**
  * Checking for a transitive closure expressed as a local search pattern matcher. The matched pattern must have two
@@ -67,12 +69,11 @@ public class BinaryTransitiveClosureCheck extends CheckOperation{
     @Override
     protected boolean check(MatchingFrame frame) throws LocalSearchException {
         Object targetValue = frame.get(targetPosition);
-        Set<Object> sourcesToEvaluate = Sets.newLinkedHashSet();
+        Queue<Object> sourcesToEvaluate = new LinkedList<>();
         sourcesToEvaluate.add(frame.get(sourcePosition));
-        Set<Object> sourceEvaluated = Sets.newHashSet();
-        do {
-            Object currentValue = sourcesToEvaluate.iterator().next();
-            sourcesToEvaluate.remove(currentValue);
+        Set<Object> sourceEvaluated = new HashSet<>();
+        while (!sourcesToEvaluate.isEmpty()) {
+            Object currentValue = sourcesToEvaluate.poll();
             sourceEvaluated.add(currentValue);
             final Object[] mappedFrame = new Object[]{currentValue, null};
             for (Tuple match : call.getAllMatches(mappedFrame)) {
@@ -83,7 +84,7 @@ public class BinaryTransitiveClosureCheck extends CheckOperation{
                     sourcesToEvaluate.add(foundTarget);
                 }
             }
-        } while (!sourcesToEvaluate.isEmpty());
+        };
         return false;
     }
     
diff --git a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/extend/ExtendBinaryTransitiveClosure.java b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/extend/ExtendBinaryTransitiveClosure.java
new file mode 100644
index 000000000..6876e8a0e
--- /dev/null
+++ b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/extend/ExtendBinaryTransitiveClosure.java
@@ -0,0 +1,137 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2013, Zoltan Ujhelyi, Istvan Rath 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:
+ *   Zoltan Ujhelyi - initial API and implementation
+ *******************************************************************************/
+package org.eclipse.viatra.query.runtime.localsearch.operations.extend;
+
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Queue;
+import java.util.Set;
+
+import org.eclipse.viatra.query.runtime.localsearch.MatchingFrame;
+import org.eclipse.viatra.query.runtime.localsearch.exceptions.LocalSearchException;
+import org.eclipse.viatra.query.runtime.localsearch.matcher.ISearchContext;
+import org.eclipse.viatra.query.runtime.localsearch.matcher.MatcherReference;
+import org.eclipse.viatra.query.runtime.localsearch.operations.CallOperationHelper;
+import org.eclipse.viatra.query.runtime.localsearch.operations.CallOperationHelper.PatternCall;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
+
+import com.google.common.collect.ImmutableMap;
+import com.google.common.collect.Lists;
+
+/**
+ * Checking for a transitive closure expressed as a local search pattern matcher. The matched pattern must have two
+ * parameters of the same model type.
+ * 
+ * @author Zoltan Ujhelyi
+ * @since 1.7
+ * 
+ */
+public abstract class ExtendBinaryTransitiveClosure extends ExtendOperation<Object> {
+
+    /**
+     * Calculates the transitive closure of a pattern match in a forward direction (first parameter bound, second
+     * unbound)
+     * 
+     * @since 1.7
+     */
+    public static class Forward extends ExtendBinaryTransitiveClosure {
+
+        public Forward(MatcherReference calledQuery, int sourcePosition, int targetPosition) {
+            super(calledQuery, sourcePosition, targetPosition);
+        }
+
+        protected Object[] calculateCallFrame(Object seed) {
+            return new Object[] { seed, null };
+        }
+
+        protected Object getTarget(Tuple frame) {
+            return frame.get(1);
+        }
+    }
+
+    /**
+     * Calculates the transitive closure of a pattern match in a backward direction (first parameter unbound, second
+     * bound)
+     * 
+     * @since 1.7
+     */
+    public static class Backward extends ExtendBinaryTransitiveClosure {
+
+        public Backward(MatcherReference calledQuery, int sourcePosition, int targetPosition) {
+            super(calledQuery, targetPosition, sourcePosition);
+        }
+
+        protected Object[] calculateCallFrame(Object seed) {
+            return new Object[] { null, seed };
+        }
+
+        protected Object getTarget(Tuple frame) {
+            return frame.get(0);
+        }
+    }
+
+    private final CallOperationHelper helper;
+    private PatternCall call;
+    private final int seedPosition;
+
+    /**
+     * The source position will be matched in the called pattern to the first parameter; while target to the second.
+     */
+    protected ExtendBinaryTransitiveClosure(MatcherReference calledQuery, int seedPosition, int targetPosition) {
+        super(targetPosition);
+        this.seedPosition = seedPosition;
+
+        helper = new CallOperationHelper(calledQuery, ImmutableMap.of(calledQuery.getQuery().getParameters().get(0),
+                seedPosition, calledQuery.getQuery().getParameters().get(1), targetPosition));
+    }
+
+    protected abstract Object[] calculateCallFrame(Object seed);
+
+    protected abstract Object getTarget(Tuple frame);
+
+    @Override
+    public void onInitialize(MatchingFrame frame, ISearchContext context) throws LocalSearchException {
+        // Note: second parameter is NOT bound during execution, but the first is
+        call = helper.createCall(context);
+
+        Queue<Object> seedsToEvaluate = new LinkedList<>();
+        seedsToEvaluate.add(frame.get(seedPosition));
+        Set<Object> seedsEvaluated = new HashSet<>();
+
+        while(!seedsToEvaluate.isEmpty()) {
+            Object currentValue = seedsToEvaluate.poll();
+            seedsEvaluated.add(currentValue);
+            final Object[] mappedFrame = calculateCallFrame(currentValue);
+            for (Tuple match : call.getAllMatches(mappedFrame)) {
+                Object foundTarget = getTarget(match);
+                if (!seedsEvaluated.contains(foundTarget)) {
+                    seedsToEvaluate.add(foundTarget);
+                }
+            }
+        }
+
+        it = seedsEvaluated.iterator();
+    }
+
+    @Override
+    public String toString() {
+        String c = helper.toString();
+        int p = c.indexOf('(');
+        return "extend    find " + c.substring(0, p) + "+" + c.substring(p);
+    }
+
+    @Override
+    public List<Integer> getVariablePositions() {
+        return Lists.asList(seedPosition, position, new Integer[0]);
+    }
+
+}
diff --git a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/extend/ExtendOperation.java b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/extend/ExtendOperation.java
index 32f7d4074..a879c912e 100644
--- a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/extend/ExtendOperation.java
+++ b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/extend/ExtendOperation.java
@@ -17,6 +17,7 @@ import org.eclipse.viatra.query.runtime.localsearch.matcher.ISearchContext;
 import org.eclipse.viatra.query.runtime.localsearch.operations.ISearchOperation;
 
 /**
+ * An operation that can be used to enumerate all possible values for a single position based on a constraint
  * @author Zoltan Ujhelyi, Akos Horvath
  * 
  */
@@ -26,7 +27,7 @@ public abstract class ExtendOperation<T> implements ISearchOperation {
     protected Iterator<T> it;
 
     /**
-     * @param position
+     * @param position the frame position all values are to be added
      */
     public ExtendOperation(int position) {
         super();
diff --git a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/planner/PConstraintInfoInferrer.java b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/planner/PConstraintInfoInferrer.java
index 7e0d20bd7..a48ee64d4 100644
--- a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/planner/PConstraintInfoInferrer.java
+++ b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/planner/PConstraintInfoInferrer.java
@@ -11,6 +11,7 @@
 package org.eclipse.viatra.query.runtime.localsearch.planner;
 
 import java.util.Collections;
+import java.util.HashSet;
 import java.util.Iterator;
 import java.util.List;
 import java.util.Set;
@@ -31,10 +32,12 @@ import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.Expressio
 import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.Inequality;
 import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.PatternMatchCounter;
 import org.eclipse.viatra.query.runtime.matchers.psystem.basicdeferred.TypeFilterConstraint;
+import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.BinaryTransitiveClosure;
 import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.ConstantValue;
 import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
 import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.TypeConstraint;
 import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PParameter;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PParameterDirection;
 import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
 
 import com.google.common.base.Function;
@@ -48,13 +51,15 @@ import com.google.common.collect.Sets;
  * @noreference This class is not intended to be referenced by clients.
  */
 class PConstraintInfoInferrer {
-
-    private static final class VariableNotDeducablePredicate implements Predicate<PVariable> {
+    
+    private static final class SingleUseVariablePredicate implements Predicate<PVariable> {
         @Override
         public boolean apply(PVariable input) {
-            return input != null && !input.isDeducable();
+            return input != null && input.getReferringConstraints().size() == 1;
         }
     }
+    
+    private static final SingleUseVariablePredicate SINGLE_USE_VARIABLE = new SingleUseVariablePredicate();
 
     private final boolean useIndex;
     private final Function<IConstraintEvaluationContext, Double> costFunction;
@@ -106,6 +111,8 @@ class PConstraintInfoInferrer {
             createConstraintInfoAggregatorConstraint(resultList, pConstraint, ((PatternMatchCounter) pConstraint).getResultVariable());   
         } else if (pConstraint instanceof PositivePatternCall){
             createConstraintInfoPositivePatternCall(resultList, (PositivePatternCall) pConstraint);
+        } else if (pConstraint instanceof BinaryTransitiveClosure) {
+            createConstraintInfoBinaryTransitiveClosure(resultList, (BinaryTransitiveClosure) pConstraint);
         } else{
             createConstraintInfoGeneric(resultList, pConstraint);
         }
@@ -156,6 +163,30 @@ class PConstraintInfoInferrer {
         doCreateConstraintInfos(resultList, pCall, affectedVariables, bindings);
     }
     
+    private void createConstraintInfoBinaryTransitiveClosure(List<PConstraintInfo> resultList, 
+            BinaryTransitiveClosure closure) {
+        // A pattern call can have any of its variables unbound
+        
+        List<PParameter> parameters = closure.getReferredQuery().getParameters();
+        Tuple variables = closure.getVariablesTuple();
+        
+        Set<Set<PVariable>> bindings = new HashSet<>();
+        PVariable firstVariable = (PVariable) variables.get(0);
+        PVariable secondVariable = (PVariable) variables.get(1);
+        // Check is always supported
+        bindings.add(Sets.newHashSet(firstVariable, secondVariable));
+        // If first parameter is not bound mandatorily, it can be left out
+        if (parameters.get(0).getDirection() != PParameterDirection.IN) {
+            bindings.add(Sets.newHashSet(secondVariable));
+        }
+        // If second parameter is not bound mandatorily, it can be left out
+        if (parameters.get(1).getDirection() != PParameterDirection.IN) {
+            bindings.add(Sets.newHashSet(firstVariable));
+        }
+        
+        doCreateConstraintInfos(resultList, closure, closure.getAffectedVariables(), bindings);
+    }
+    
     
 
     private void createConstraintInfoExportedParameter(List<PConstraintInfo> resultList, 
@@ -196,8 +227,8 @@ class PConstraintInfoInferrer {
             PConstraint pConstraint, PVariable resultVariable){
         Set<PVariable> affectedVariables = pConstraint.getAffectedVariables();
         
-        // The only variables which can be unbound are the ones which cannot be deduced by any constraint and the result variable
-        Set<PVariable> canBeUnboundVariables = Sets.union(Collections.singleton(resultVariable), Sets.filter(affectedVariables, new VariableNotDeducablePredicate()));
+        // The only variables which can be unbound are single-use
+        Set<PVariable> canBeUnboundVariables = Sets.union(Collections.singleton(resultVariable), Sets.filter(affectedVariables, SINGLE_USE_VARIABLE));
        
         Set<Set<PVariable>> bindings = calculatePossibleBindings(canBeUnboundVariables, affectedVariables);
         
@@ -225,8 +256,8 @@ class PConstraintInfoInferrer {
     private void createConstraintInfoGeneric(List<PConstraintInfo> resultList, PConstraint pConstraint){
         Set<PVariable> affectedVariables = pConstraint.getAffectedVariables();
         
-        // The only variables which can be unbound are the ones which cannot be deduced by any constraint
-        Set<PVariable> canBeUnboundVariables = Sets.filter(affectedVariables, new VariableNotDeducablePredicate());
+        // The only variables which can be unbound are single use variables
+        Set<PVariable> canBeUnboundVariables = Sets.filter(affectedVariables, SINGLE_USE_VARIABLE);
        
         Set<Set<PVariable>> bindings = calculatePossibleBindings(canBeUnboundVariables, affectedVariables);
         
diff --git a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/planner/POperationCompiler.java b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/planner/POperationCompiler.java
index cfab7c6bb..b68d68ca8 100644
--- a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/planner/POperationCompiler.java
+++ b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/planner/POperationCompiler.java
@@ -41,6 +41,7 @@ import org.eclipse.viatra.query.runtime.localsearch.operations.check.nobase.Scop
 import org.eclipse.viatra.query.runtime.localsearch.operations.extend.AggregatorExtend;
 import org.eclipse.viatra.query.runtime.localsearch.operations.extend.CountOperation;
 import org.eclipse.viatra.query.runtime.localsearch.operations.extend.ExpressionEval;
+import org.eclipse.viatra.query.runtime.localsearch.operations.extend.ExtendBinaryTransitiveClosure;
 import org.eclipse.viatra.query.runtime.localsearch.operations.extend.ExtendConstant;
 import org.eclipse.viatra.query.runtime.localsearch.operations.extend.ExtendPositivePatternCall;
 import org.eclipse.viatra.query.runtime.localsearch.operations.extend.ExtendToEStructuralFeatureSource;
@@ -406,6 +407,8 @@ public class POperationCompiler {
             createExtend((ConstantValue) pConstraint, variableMapping);
         } else if (pConstraint instanceof TypeConstraint) {
             createExtend((TypeConstraint) pConstraint, variableMapping);
+        } else if (pConstraint instanceof BinaryTransitiveClosure) {
+            createExtend((BinaryTransitiveClosure)pConstraint, variableMapping);
         } else {
             String msg = "Unsupported Extend constraint: "+pConstraint.toString();
             throw new QueryProcessingException(msg, null, msg, null);
@@ -419,6 +422,29 @@ public class POperationCompiler {
         dependencies.add(matcherReference);
     }
 
+    private void createExtend(BinaryTransitiveClosure binaryTransitiveClosure, Map<PVariable, Integer> variableMapping) throws QueryProcessingException {
+        int sourcePosition = variableMapping.get(binaryTransitiveClosure.getVariablesTuple().get(0));
+        int targetPosition = variableMapping.get(binaryTransitiveClosure.getVariablesTuple().get(1));
+        
+        PQuery referredQuery = binaryTransitiveClosure.getReferredQuery();
+        
+        boolean sourceBound = variableBindings.get(binaryTransitiveClosure).contains(sourcePosition);
+        boolean targetBound = variableBindings.get(binaryTransitiveClosure).contains(targetPosition);
+        
+        if (sourceBound && !targetBound) {
+            Set<PParameter> adornment = ImmutableSet.of(referredQuery.getParameters().get(0));
+            operations.add(new ExtendBinaryTransitiveClosure.Forward(new MatcherReference(referredQuery, adornment), sourcePosition, targetPosition));
+            dependencies.add(new MatcherReference(referredQuery, adornment));            
+        } else if (!sourceBound && targetBound) {
+            Set<PParameter> adornment = ImmutableSet.of(referredQuery.getParameters().get(1));
+            operations.add(new ExtendBinaryTransitiveClosure.Backward(new MatcherReference(referredQuery, adornment), sourcePosition, targetPosition));
+            dependencies.add(new MatcherReference(referredQuery, adornment));                        
+        } else {
+            String msg = "Binary transitive closure not supported with two unbound parameters";
+            throw new QueryProcessingException(msg, null, msg, binaryTransitiveClosure.getPSystem().getPattern());
+        }
+    }
+    
     private void createExtend(ConstantValue constant, Map<PVariable, Integer> variableMapping) {
         int position = variableMapping.get(constant.getVariablesTuple().get(0));
         operations.add(new ExtendConstant(position, constant.getSupplierKey()));