[441323] Binary transitive closure implementation with Base

For incremental pattern matcher calls it makes sense to use the IncSCC
algorithm from base (similar to the TransitiveClosureNode in Rete) to
calculate transitive closures efficiently.

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

4 files changed, 261 insertions, 1 deletions

diff --git a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/META-INF/MANIFEST.MF b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/META-INF/MANIFEST.MF
index af30c68c7..8abfd4ef1 100644
--- a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/META-INF/MANIFEST.MF
+++ b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/META-INF/MANIFEST.MF
@@ -9,7 +9,8 @@ Require-Bundle: org.eclipse.viatra.query.runtime.base;bundle-version="[1.7.0,1.8
  org.eclipse.emf.ecore;bundle-version="2.8.3",
  org.eclipse.viatra.query.runtime;bundle-version="[1.7.0,1.8.0)",
  org.eclipse.viatra.query.runtime.matchers;bundle-version="[1.7.0,1.8.0)",
- org.eclipse.xtext.xbase.lib;bundle-version="2.9.0"
+ org.eclipse.xtext.xbase.lib;bundle-version="2.9.0",
+ org.eclipse.viatra.query.runtime.base.itc;bundle-version="[1.7.0,1.8.0)"
 Export-Package: org.eclipse.viatra.query.runtime.localsearch,
  org.eclipse.viatra.query.runtime.localsearch.exceptions,
  org.eclipse.viatra.query.runtime.localsearch.matcher;
diff --git a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/CallOperationHelper.java b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/CallOperationHelper.java
index 4c598ec30..7a1cd4abc 100644
--- a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/CallOperationHelper.java
+++ b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/CallOperationHelper.java
@@ -22,6 +22,7 @@ import org.eclipse.viatra.query.runtime.localsearch.exceptions.LocalSearchExcept
 import org.eclipse.viatra.query.runtime.localsearch.matcher.ISearchContext;
 import org.eclipse.viatra.query.runtime.localsearch.matcher.MatcherReference;
 import org.eclipse.viatra.query.runtime.matchers.backend.IQueryResultProvider;
+import org.eclipse.viatra.query.runtime.matchers.backend.IUpdateable;
 import org.eclipse.viatra.query.runtime.matchers.psystem.aggregations.IMultisetAggregationOperator;
 import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PParameter;
 import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PQuery;
@@ -144,6 +145,19 @@ public class CallOperationHelper {
             return matcher.getAllMatches(mapFrame(frameInCaller));
         }
         
+        /**
+         * @since 1.7
+         */
+        public void registerChangeListener(IUpdateable listener) {
+            matcher.addUpdateListener(listener, listener, true);
+        }
+        
+        /**
+         * @since 1.7
+         */
+        public void removeChangeListener(IUpdateable listener) {
+            matcher.removeUpdateListener(listener);
+        }
     }
     
     /**
@@ -197,6 +211,13 @@ public class CallOperationHelper {
         return variables;
     }
     
+    /**
+     * @since 1.7
+     */
+    public PQuery getCalledQuery() {
+        return calledQuery;
+    }
+
     @Override
     public String toString() {
         return calledQuery.getFullyQualifiedName()+"("+Joiner.on(",").join(
diff --git a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/TransitiveClosureGraph.java b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/TransitiveClosureGraph.java
new file mode 100644
index 000000000..5162e89d7
--- /dev/null
+++ b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/TransitiveClosureGraph.java
@@ -0,0 +1,119 @@
+/*******************************************************************************
+ * Copyright (c) 2010-2017, Zoltan Ujhelyi, IncQuery Labs Ltd.
+ * 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;
+
+import java.util.Objects;
+
+import org.eclipse.viatra.query.runtime.base.itc.alg.incscc.IncSCCAlg;
+import org.eclipse.viatra.query.runtime.base.itc.graphimpl.Graph;
+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.operations.CallOperationHelper.PatternCall;
+import org.eclipse.viatra.query.runtime.matchers.backend.IUpdateable;
+import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PQuery;
+import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple;
+import org.eclipse.viatra.query.runtime.matchers.util.IProvider;
+
+/**
+ * Generic helper for calculating and accessing transitive closures of called incremental graph patterns. Such a graph
+ * can be shared between all call adornments.
+ * 
+ * @author Zoltan Ujhelyi
+ * @since 1.7
+ */
+public class TransitiveClosureGraph implements IUpdateable {
+
+    private Graph<Object> graph = new Graph<>();
+    private IncSCCAlg<Object> tcAlg = new IncSCCAlg<Object>(graph);
+    private PatternCall call;
+
+    private static final class TransitiveClosureGraphKey {
+        private final PQuery query;
+
+        private TransitiveClosureGraphKey(PQuery query) {
+            this.query = query;
+        }
+
+        @Override
+        public int hashCode() {
+            return query.hashCode();
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            if (this == obj)
+                return true;
+            if (obj == null)
+                return false;
+            if (getClass() != obj.getClass())
+                return false;
+            TransitiveClosureGraphKey other = (TransitiveClosureGraphKey) obj;
+            return Objects.equals(query, other.query);
+        }
+
+    }
+
+    public static TransitiveClosureGraph accessClosureGraph(final ISearchContext context,
+            final CallOperationHelper helper) {
+        return context.accessBackendLevelCache(new TransitiveClosureGraphKey(helper.getCalledQuery()),
+                TransitiveClosureGraph.class, new IProvider<TransitiveClosureGraph>() {
+
+                    @Override
+                    public TransitiveClosureGraph get() {
+                        try {
+                            return new TransitiveClosureGraph(helper, context);
+                        } catch (LocalSearchException e) {
+                            throw new RuntimeException(e);
+                        }
+                    }
+                });
+    }
+
+    private TransitiveClosureGraph(CallOperationHelper helper, ISearchContext context) throws LocalSearchException {
+        call = helper.createCall(context);
+        call.registerChangeListener(this);
+
+    }
+
+    @Override
+    public void update(Tuple updateElement, boolean isInsertion) {
+        Object sourceNode = updateElement.get(0);
+        Object targetNode = updateElement.get(1);
+        if (isInsertion) {
+            graph.insertNode(sourceNode); // Ensure source is added
+            graph.insertNode(targetNode); // Ensure target is added
+            graph.insertEdge(sourceNode, targetNode);
+        } else {
+            graph.deleteEdge(sourceNode, targetNode);
+
+            if (tcAlg.isIsolated(sourceNode)) {
+                graph.deleteNode(sourceNode);
+            }
+            if (!Objects.equals(sourceNode, targetNode) && tcAlg.isIsolated(targetNode)) {
+                graph.deleteNode(targetNode);
+            }
+        }
+
+    }
+
+    public Iterable<Object> getAllSources(Object target) {
+        return tcAlg.getAllReachableSources(target);
+    }
+
+    public Iterable<Object> getAllTargets(Object source) {
+        return tcAlg.getAllReachableTargets(source);
+    }
+
+    public void dispose() {
+        call.removeChangeListener(this);
+        tcAlg.dispose();
+    }
+}
diff --git a/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/extend/ExtendBinaryTransitiveClosureIncremental.java b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/extend/ExtendBinaryTransitiveClosureIncremental.java
new file mode 100644
index 000000000..cbe05cf8c
--- /dev/null
+++ b/query/plugins/org.eclipse.viatra.query.runtime.localsearch/src/org/eclipse/viatra/query/runtime/localsearch/operations/extend/ExtendBinaryTransitiveClosureIncremental.java
@@ -0,0 +1,119 @@
+/*******************************************************************************
+ * 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.List;
+
+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.TransitiveClosureGraph;
+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 ExtendBinaryTransitiveClosureIncremental 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 ExtendBinaryTransitiveClosureIncremental {
+
+        public Forward(MatcherReference calledQuery, int sourcePosition, int targetPosition) {
+            super(calledQuery, sourcePosition, targetPosition);
+        }
+        
+        @Override
+        protected Object getSource(Tuple frame) {
+            return frame.get(1);
+        }
+
+        @Override
+        protected Iterable<Object> getTargets(Tuple frame, TransitiveClosureGraph closure) {
+            return closure.getAllSources(frame.get(0));
+        }
+    }
+
+    /**
+     * 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 ExtendBinaryTransitiveClosureIncremental {
+
+        public Backward(MatcherReference calledQuery, int sourcePosition, int targetPosition) {
+            super(calledQuery, targetPosition, sourcePosition);
+        }
+
+        @Override
+        protected Object getSource(Tuple frame) {
+            return frame.get(1);
+        }
+        
+        @Override
+        protected Iterable<Object> getTargets(Tuple frame, TransitiveClosureGraph closure) {
+            return closure.getAllSources(frame.get(1));
+        }
+
+    }
+
+    private final CallOperationHelper helper;
+    private final int seedPosition;
+
+    /**
+     * The source position will be matched in the called pattern to the first parameter; while target to the second.
+     */
+    protected ExtendBinaryTransitiveClosureIncremental(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 getSource(Tuple frame);
+    protected abstract Iterable<Object> getTargets(Tuple frame, TransitiveClosureGraph closure);
+
+    @Override
+    public void onInitialize(MatchingFrame frame, ISearchContext context) throws LocalSearchException {
+        TransitiveClosureGraph closure = TransitiveClosureGraph.accessClosureGraph(context, helper);
+
+        it = getTargets(frame, closure).iterator();
+    }
+
+    @Override
+    public String toString() {
+        String c = helper.toString();
+        int p = c.indexOf('(');
+        return "extend    find " + c.substring(0, p) + "+" + c.substring(p) + "[incremental]";
+    }
+
+    @Override
+    public List<Integer> getVariablePositions() {
+        return Lists.asList(seedPosition, position, new Integer[0]);
+    }
+
+}