1 files changed, 413 insertions, 0 deletions

diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/StatisticsBasedConstraintCostFunction.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/StatisticsBasedConstraintCostFunction.java
new file mode 100644
index 00000000..873be31d
--- /dev/null
+++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/cost/impl/StatisticsBasedConstraintCostFunction.java
@@ -0,0 +1,413 @@
+/**
+ * Copyright (c) 2010-2016, Grill Balázs, IncQuery Labs Ltd.
+ * This program and the accompanying materials are made available under the
+ * terms of the Eclipse Public License v. 2.0 which is available at
+ * http://www.eclipse.org/legal/epl-v20.html.
+ * 
+ * SPDX-License-Identifier: EPL-2.0
+ */
+package tools.refinery.viatra.runtime.localsearch.planner.cost.impl;
+
+import static tools.refinery.viatra.runtime.matchers.planning.helpers.StatisticsHelper.min;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.List;
+import java.util.Map;
+import java.util.Optional;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.localsearch.matcher.integration.AbstractLocalSearchResultProvider;
+import tools.refinery.viatra.runtime.localsearch.planner.cost.IConstraintEvaluationContext;
+import tools.refinery.viatra.runtime.localsearch.planner.cost.ICostFunction;
+import tools.refinery.viatra.runtime.matchers.ViatraQueryRuntimeException;
+import tools.refinery.viatra.runtime.matchers.backend.IQueryResultProvider;
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.planning.helpers.FunctionalDependencyHelper;
+import tools.refinery.viatra.runtime.matchers.psystem.IQueryReference;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
+import tools.refinery.viatra.runtime.matchers.psystem.analysis.QueryAnalyzer;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.AggregatorConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExportedParameter;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.ExpressionEvaluation;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.Inequality;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.NegativePatternCall;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.PatternMatchCounter;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.TypeFilterConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.BinaryReflexiveTransitiveClosure;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.BinaryTransitiveClosure;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.ConstantValue;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.PositivePatternCall;
+import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.TypeConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameter;
+import tools.refinery.viatra.runtime.matchers.tuple.TupleMask;
+import tools.refinery.viatra.runtime.matchers.util.Accuracy;
+import tools.refinery.viatra.runtime.matchers.util.Preconditions;
+
+/**
+ * Cost function which calculates cost based on the cardinality of items in the runtime model
+ * 
+ * <p> To provide custom statistics, override 
+ *  {@link #projectionSize(IConstraintEvaluationContext, IInputKey, TupleMask, Accuracy)} 
+ *  and {@link #bucketSize(IQueryReference, IConstraintEvaluationContext, TupleMask)}.
+ * 
+ * @author Grill Balázs
+ * @since 1.4
+ */
+public abstract class StatisticsBasedConstraintCostFunction implements ICostFunction {
+    protected static final double MAX_COST = 250.0;
+
+    protected static final double DEFAULT_COST = StatisticsBasedConstraintCostFunction.MAX_COST - 100.0;
+        
+    /**
+     * @since 2.1
+     */
+    public static final double INVERSE_NAVIGATION_PENALTY_DEFAULT = 0.10;
+    /**
+     * @since 2.1
+     */
+    public static final double INVERSE_NAVIGATION_PENALTY_GENERIC = 0.01;
+    /**
+     * @since 2.7
+     */
+    public static final double EVAL_UNWIND_EXTENSION_FACTOR = 3.0;
+    
+    private final double inverseNavigationPenalty;
+    
+    
+    /**
+     * @since 2.1
+     */
+    public StatisticsBasedConstraintCostFunction(double inverseNavigationPenalty) {
+        super();
+        this.inverseNavigationPenalty = inverseNavigationPenalty;
+    }
+    public StatisticsBasedConstraintCostFunction() {
+        this(INVERSE_NAVIGATION_PENALTY_DEFAULT);
+    }
+
+    /**
+     * @deprecated call and implement {@link #projectionSize(IConstraintEvaluationContext, IInputKey, TupleMask, Accuracy)} instead
+     */
+    @Deprecated
+    public long countTuples(final IConstraintEvaluationContext input, final IInputKey supplierKey) {
+        return projectionSize(input, supplierKey, TupleMask.identity(supplierKey.getArity()), Accuracy.EXACT_COUNT).orElse(-1L);
+    }
+    
+    /**
+     * Override this to provide custom statistics on edge/node counts.
+     * New implementors shall implement this instead of {@link #countTuples(IConstraintEvaluationContext, IInputKey)}
+     * @since 2.1
+     */
+    public Optional<Long> projectionSize(final IConstraintEvaluationContext input, final IInputKey supplierKey,
+            final TupleMask groupMask, Accuracy requiredAccuracy) {
+        long legacyCount = countTuples(input, supplierKey);
+        return legacyCount < 0 ? Optional.empty() : Optional.of(legacyCount);
+    }
+
+    /**
+     * Override this to provide custom estimates for match set sizes of called patterns.
+     * @since 2.1
+     */
+    public Optional<Double> bucketSize(final IQueryReference patternCall,
+            final IConstraintEvaluationContext input, TupleMask projMask) {
+        IQueryResultProvider resultProvider = input.resultProviderRequestor().requestResultProvider(patternCall, null);
+        // TODO hack: use LS cost instead of true bucket size estimate
+        if (resultProvider instanceof AbstractLocalSearchResultProvider) {
+            double estimatedCost = ((AbstractLocalSearchResultProvider) resultProvider).estimateCost(projMask);
+            return Optional.of(estimatedCost);
+        } else {            
+            return resultProvider.estimateAverageBucketSize(projMask, Accuracy.APPROXIMATION);
+        }
+    }
+   
+    
+
+    @Override
+    public double apply(final IConstraintEvaluationContext input) {
+        return this.calculateCost(input.getConstraint(), input);
+    }
+
+    protected double _calculateCost(final ConstantValue constant, final IConstraintEvaluationContext input) {
+        return 0.0f;
+    }
+
+    protected double _calculateCost(final TypeConstraint constraint, final IConstraintEvaluationContext input) {
+        final Collection<PVariable> freeMaskVariables = input.getFreeVariables();
+        final Collection<PVariable> boundMaskVariables = input.getBoundVariables();
+        IInputKey supplierKey = constraint.getSupplierKey();
+        long arity = supplierKey.getArity();
+
+        if ((arity == 1)) {
+            // unary constraint
+            return calculateUnaryConstraintCost(constraint, input);
+        } else if ((arity == 2)) {
+            // binary constraint
+            PVariable srcVariable = ((PVariable) constraint.getVariablesTuple().get(0));
+            PVariable dstVariable = ((PVariable) constraint.getVariablesTuple().get(1));
+            boolean isInverse = false;
+            // Check if inverse navigation is needed along the edge
+            if ((freeMaskVariables.contains(srcVariable) && boundMaskVariables.contains(dstVariable))) {
+                isInverse = true;
+            }
+            double binaryExtendCost = calculateBinaryCost(supplierKey, srcVariable, dstVariable, isInverse, input);
+            // Make inverse navigation slightly more expensive than forward navigation
+            // See https://bugs.eclipse.org/bugs/show_bug.cgi?id=501078
+            return (isInverse) ? binaryExtendCost + inverseNavigationPenalty : binaryExtendCost;
+        } else {
+            // n-ary constraint
+            throw new UnsupportedOperationException("Cost calculation for arity " + arity + " is not implemented yet");
+        }
+    }
+
+    
+    /**
+     * @deprecated use/implement {@link #calculateBinaryCost(IInputKey, PVariable, PVariable, boolean, IConstraintEvaluationContext)} instead
+     */
+    @Deprecated
+    protected double calculateBinaryExtendCost(final IInputKey supplierKey, final PVariable srcVariable,
+            final PVariable dstVariable, final boolean isInverse, long edgeCount /* TODO remove */,
+            final IConstraintEvaluationContext input) {
+        throw new UnsupportedOperationException();
+    }
+    
+    /**
+     * @since 2.1
+     */
+    protected double calculateBinaryCost(final IInputKey supplierKey, final PVariable srcVariable,
+            final PVariable dstVariable, final boolean isInverse, 
+            final IConstraintEvaluationContext input) {
+        final Collection<PVariable> freeMaskVariables = input.getFreeVariables();
+        final PConstraint constraint = input.getConstraint();
+        
+//        IQueryMetaContext metaContext = input.getRuntimeContext().getMetaContext();
+//        Collection<InputKeyImplication> implications = metaContext.getImplications(supplierKey);
+
+        Optional<Long> edgeUpper = projectionSize(input,   supplierKey,    TupleMask.identity(2),          Accuracy.BEST_UPPER_BOUND);
+        Optional<Long> srcUpper  = projectionSize(input,   supplierKey,    TupleMask.selectSingle(0, 2),   Accuracy.BEST_UPPER_BOUND);
+        Optional<Long> dstUpper  = projectionSize(input,   supplierKey,    TupleMask.selectSingle(1, 2),   Accuracy.BEST_UPPER_BOUND);
+
+        if (freeMaskVariables.contains(srcVariable) && freeMaskVariables.contains(dstVariable)) {
+            Double branchCount = edgeUpper.map(Long::doubleValue).orElse(
+                    srcUpper.map(Long::doubleValue).orElse(DEFAULT_COST)
+                    *
+                    dstUpper.map(Long::doubleValue).orElse(DEFAULT_COST)
+            );      
+            return branchCount;
+            
+        } else {
+            
+            Optional<Long> srcLower  = projectionSize(input,   supplierKey,    TupleMask.selectSingle(0, 2),   Accuracy.APPROXIMATION);
+            Optional<Long> dstLower  = projectionSize(input,   supplierKey,    TupleMask.selectSingle(1, 2),   Accuracy.APPROXIMATION);
+            
+            List<Optional<Long>> nodeLower = Arrays.asList(srcLower, dstLower);
+            List<Optional<Long>> nodeUpper = Arrays.asList(srcUpper, dstUpper);
+            
+            int from = isInverse ? 1 : 0;
+            int to   = isInverse ? 0 : 1;
+            
+            Optional<Double> costEstimate = Optional.empty();
+            
+            if (!freeMaskVariables.contains(srcVariable) && !freeMaskVariables.contains(dstVariable)) {
+                // both variables bound, this is a simple check
+                costEstimate = min(costEstimate, 0.9);
+            } // TODO use bucket size estimation in the runtime context
+            costEstimate = min(costEstimate, 
+                edgeUpper.flatMap(edges -> 
+                nodeLower.get(from).map(fromNodes ->
+                    // amortize edges over start nodes
+                    (fromNodes == 0) ? 0.0 : (((double) edges) / fromNodes)
+            )));
+            if (navigatesThroughFunctionalDependencyInverse(input, constraint)) {
+                costEstimate = min(costEstimate, nodeUpper.get(to).flatMap(toNodes -> 
+                        nodeLower.get(from).map(fromNodes ->
+                        // due to a reverse functional dependency, the destination count is an upper bound for the edge count
+                        (fromNodes == 0) ? 0.0 : ((double) toNodes) / fromNodes
+                    )));
+            }
+            if (! edgeUpper.isPresent()) {
+                costEstimate = min(costEstimate, nodeUpper.get(to).flatMap(toNodes -> 
+                        nodeLower.get(from).map(fromNodes ->
+                        // If count is 0, no such element exists in the model, so there will be no branching
+                        // TODO rethink, why dstNodeCount / srcNodeCount instead of dstNodeCount? 
+                        // The universally valid bound would be something like sparseEdgeEstimate = dstNodeCount + 1.0
+                        // If we assume sparseness, we can reduce it by a SPARSENESS_FACTOR (e.g. 0.1). 
+                        // Alternatively, discount dstNodeCount * srcNodeCount on a SPARSENESS_EXPONENT (e.g 0.75) and then amortize over srcNodeCount.
+                        fromNodes != 0 ? Math.max(1.0, ((double) toNodes) / fromNodes) : 1.0
+                    )));
+            } 
+            if (navigatesThroughFunctionalDependency(input, constraint)) {
+                // At most one destination value
+                costEstimate = min(costEstimate, 1.0); 
+            }
+            
+            return costEstimate.orElse(DEFAULT_COST);
+
+        }
+    }
+
+    /**
+     * @since 1.7
+     */
+    protected boolean navigatesThroughFunctionalDependency(final IConstraintEvaluationContext input,
+            final PConstraint constraint) {
+        return navigatesThroughFunctionalDependency(input, constraint, input.getBoundVariables(), input.getFreeVariables());
+    }
+    /**
+     * @since 2.1
+     */
+    protected boolean navigatesThroughFunctionalDependencyInverse(final IConstraintEvaluationContext input,
+            final PConstraint constraint) {
+        return navigatesThroughFunctionalDependency(input, constraint, input.getFreeVariables(), input.getBoundVariables());
+    }
+    /**
+     * @since 2.1
+     */
+    protected boolean navigatesThroughFunctionalDependency(final IConstraintEvaluationContext input,
+            final PConstraint constraint, Collection<PVariable> determining, Collection<PVariable> determined) {
+        final QueryAnalyzer queryAnalyzer = input.getQueryAnalyzer();
+        final Map<Set<PVariable>, Set<PVariable>> functionalDependencies = queryAnalyzer
+                .getFunctionalDependencies(Collections.singleton(constraint), false);
+        final Set<PVariable> impliedVariables = FunctionalDependencyHelper.closureOf(determining,
+                functionalDependencies);
+        return ((impliedVariables != null) && impliedVariables.containsAll(determined));
+    }
+    
+    protected double calculateUnaryConstraintCost(final TypeConstraint constraint,
+            final IConstraintEvaluationContext input) {
+        PVariable variable = (PVariable) constraint.getVariablesTuple().get(0);
+        if (input.getBoundVariables().contains(variable)) {
+            return 0.9;
+        } else {
+            return projectionSize(input, constraint.getSupplierKey(), TupleMask.identity(1), Accuracy.APPROXIMATION)
+                    .map(count -> 1.0 + count).orElse(DEFAULT_COST);
+        }
+    }
+
+    protected double _calculateCost(final ExportedParameter exportedParam, final IConstraintEvaluationContext input) {
+        return 0.0;
+    }
+
+    protected double _calculateCost(final TypeFilterConstraint exportedParam,
+            final IConstraintEvaluationContext input) {
+        return 0.0;
+    }
+
+    protected double _calculateCost(final PositivePatternCall patternCall, final IConstraintEvaluationContext input) {
+        final List<Integer> boundPositions = new ArrayList<>();
+        final List<PParameter> parameters = patternCall.getReferredQuery().getParameters();
+        for (int i = 0; (i < parameters.size()); i++) {
+            final PVariable variable = patternCall.getVariableInTuple(i);
+            if (input.getBoundVariables().contains(variable)) boundPositions.add(i);
+        }
+        TupleMask projMask = TupleMask.fromSelectedIndices(parameters.size(), boundPositions);
+        
+        return bucketSize(patternCall, input, projMask).orElse(DEFAULT_COST);        
+    }
+
+
+    /**
+     * @since 1.7
+     */
+    protected double _calculateCost(final ExpressionEvaluation evaluation, final IConstraintEvaluationContext input) {
+        // Even if there are multiple results here, if all output variable is bound eval unwind will not result in
+        // multiple branches in search graph
+        final double multiplier = evaluation.isUnwinding() && !input.getFreeVariables().isEmpty()
+                ? EVAL_UNWIND_EXTENSION_FACTOR
+                : 1.0;
+        return _calculateCost((PConstraint) evaluation, input) * multiplier;
+    }
+    
+    /**
+     * @since 1.7
+     */
+    protected double _calculateCost(final Inequality inequality, final IConstraintEvaluationContext input) {
+        return _calculateCost((PConstraint)inequality, input);
+    }
+    
+    /**
+     * @since 1.7
+     */
+    protected double _calculateCost(final AggregatorConstraint aggregator, final IConstraintEvaluationContext input) {
+        return _calculateCost((PConstraint)aggregator, input);
+    }
+    
+    /**
+     * @since 1.7
+     */
+    protected double _calculateCost(final NegativePatternCall call, final IConstraintEvaluationContext input) {
+        return _calculateCost((PConstraint)call, input);
+    }
+    
+    /**
+     * @since 1.7
+     */
+    protected double _calculateCost(final PatternMatchCounter counter, final IConstraintEvaluationContext input) {
+        return _calculateCost((PConstraint)counter, input);
+    }
+    
+    /**
+     * @since 1.7
+     */
+    protected double _calculateCost(final BinaryTransitiveClosure closure, final IConstraintEvaluationContext input) {
+        // if (input.getFreeVariables().size() == 1) return 3.0; 
+        return StatisticsBasedConstraintCostFunction.DEFAULT_COST;
+    }
+    
+    /**
+     * @since 2.0
+     */
+    protected double _calculateCost(final BinaryReflexiveTransitiveClosure closure, final IConstraintEvaluationContext input) {
+        // if (input.getFreeVariables().size() == 1) return 3.0; 
+        return StatisticsBasedConstraintCostFunction.DEFAULT_COST;
+    }
+    
+    /**
+     * Default cost calculation strategy
+     */
+    protected double _calculateCost(final PConstraint constraint, final IConstraintEvaluationContext input) {
+        if (input.getFreeVariables().isEmpty()) {
+            return 1.0;
+        } else {
+            return StatisticsBasedConstraintCostFunction.DEFAULT_COST;
+        }
+    }
+
+    /**
+     * @throws ViatraQueryRuntimeException
+     */
+    public double calculateCost(final PConstraint constraint, final IConstraintEvaluationContext input) {
+        Preconditions.checkArgument(constraint != null, "Set constraint value correctly");
+        if (constraint instanceof ExportedParameter) {
+            return _calculateCost((ExportedParameter) constraint, input);
+        } else if (constraint instanceof TypeFilterConstraint) {
+            return _calculateCost((TypeFilterConstraint) constraint, input);
+        } else if (constraint instanceof ConstantValue) {
+            return _calculateCost((ConstantValue) constraint, input);
+        } else if (constraint instanceof PositivePatternCall) {
+            return _calculateCost((PositivePatternCall) constraint, input);
+        } else if (constraint instanceof TypeConstraint) {
+            return _calculateCost((TypeConstraint) constraint, input);
+        } else if (constraint instanceof ExpressionEvaluation) {
+            return _calculateCost((ExpressionEvaluation) constraint, input);
+        } else if (constraint instanceof Inequality) {
+            return _calculateCost((Inequality) constraint, input);
+        } else if (constraint instanceof AggregatorConstraint) {
+            return _calculateCost((AggregatorConstraint) constraint, input);
+        } else if (constraint instanceof NegativePatternCall) {
+            return _calculateCost((NegativePatternCall) constraint, input);
+        } else if (constraint instanceof PatternMatchCounter) {
+            return _calculateCost((PatternMatchCounter) constraint, input);
+        } else if (constraint instanceof BinaryTransitiveClosure) {
+            return _calculateCost((BinaryTransitiveClosure) constraint, input);
+        } else if (constraint instanceof BinaryReflexiveTransitiveClosure) {
+            return _calculateCost((BinaryReflexiveTransitiveClosure) constraint, input);
+        } else {
+            // Default cost calculation
+            return _calculateCost(constraint, input);
+        }
+    }
+}