1 files changed, 310 insertions, 0 deletions

diff --git a/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PBodyNormalizer.java b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PBodyNormalizer.java
new file mode 100644
index 00000000..90943129
--- /dev/null
+++ b/subprojects/viatra-runtime/src/main/java/tools/refinery/viatra/runtime/matchers/psystem/rewriters/PBodyNormalizer.java
@@ -0,0 +1,310 @@
+/*******************************************************************************
+ * Copyright (c) 2004-2010 Gabor Bergmann and Daniel Varro
+ * 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.matchers.psystem.rewriters;
+
+import java.util.ArrayList;
+import java.util.Collection;
+import java.util.Collections;
+import java.util.Comparator;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.LinkedHashSet;
+import java.util.LinkedList;
+import java.util.List;
+import java.util.Map;
+import java.util.Queue;
+import java.util.Set;
+
+import tools.refinery.viatra.runtime.matchers.context.IInputKey;
+import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
+import tools.refinery.viatra.runtime.matchers.planning.QueryProcessingException;
+import tools.refinery.viatra.runtime.matchers.planning.helpers.TypeHelper;
+import tools.refinery.viatra.runtime.matchers.psystem.ITypeConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.ITypeInfoProviderConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.PBody;
+import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
+import tools.refinery.viatra.runtime.matchers.psystem.TypeJudgement;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.Equality;
+import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.Inequality;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PDisjunction;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery;
+import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery.PQueryStatus;
+import tools.refinery.viatra.runtime.matchers.util.CollectionsFactory;
+
+/**
+ * A disjunction rewriter for creating a normalized form of specification, unifying variables and running basic sanity
+ * checks. This rewriter does not copy but modifies directly the original specification, requiring a mutable
+ * disjunction.
+ * 
+ * @author Gabor Bergmann
+ * 
+ */
+public class PBodyNormalizer extends PDisjunctionRewriter {
+
+    private IQueryMetaContext context;
+
+    public PBodyNormalizer(IQueryMetaContext context) {
+        this.context = context;
+    }
+
+    /**
+     * Returns whether unary constraint elimination is enabled. This behavior can be customized by creating a subclass
+     * with a custom implementation.
+     * 
+     * @since 1.6
+     */
+    protected boolean shouldCalculateImpliedTypes(PQuery query) {
+        return true;
+    }
+
+    /**
+     * Returns whether 'weakened alternative' suggestions of the context shall be expanded as additional PConstraints. 
+     * This behavior can be customized by creating a subclass
+     * with a custom implementation.
+     * 
+     * @since 1.6
+     */
+    protected boolean shouldExpandWeakenedAlternatives(PQuery query) {
+        return false;
+    }
+
+    @Override
+    public PDisjunction rewrite(PDisjunction disjunction) {
+        Set<PBody> normalizedBodies = new LinkedHashSet<>();
+        for (PBody body : disjunction.getBodies()) {
+            PBodyCopier copier = new PBodyCopier(body, getTraceCollector());
+            PBody modifiedBody = copier.getCopiedBody();
+            normalizeBody(modifiedBody);
+            normalizedBodies.add(modifiedBody);
+            modifiedBody.setStatus(PQueryStatus.OK);
+        }
+        return new PDisjunction(normalizedBodies);
+    }
+
+    public void setContext(IQueryMetaContext context) {
+        this.context = context;
+    }
+
+    /**
+     * Provides a normalized version of the pattern body. May return a different version than the original version if
+     * needed.
+     * 
+     * @param body
+     */
+    public PBody normalizeBody(PBody body) {
+        try {
+            return normalizeBodyInternal(body);
+        } catch (QueryProcessingException e) {
+            throw new RewriterException("Error during rewriting: {1}", new String[] { e.getMessage() },
+                    e.getShortMessage(), body.getPattern(), e);
+        }
+    }
+
+    PBody normalizeBodyInternal(PBody body) {
+        // UNIFICATION AND WEAK INEQUALITY ELIMINATION
+        unifyVariablesAlongEqualities(body);
+        eliminateWeakInequalities(body);
+        removeMootEqualities(body);
+
+        // ADDING WEAKENED ALTERNATIVES
+        if (shouldExpandWeakenedAlternatives(body.getPattern())) {
+            expandWeakenedAlternativeConstraints(body);
+        }
+        
+        // CONSTRAINT ELIMINATION WITH TYPE INFERENCE
+        if (shouldCalculateImpliedTypes(body.getPattern())) {
+            eliminateInferrableTypes(body, context);
+        } else {
+            // ELIMINATE DUPLICATE TYPE CONSTRAINTS
+            eliminateDuplicateTypeConstraints(body);
+        }
+
+        
+        // PREVENTIVE CHECKS
+        checkSanity(body);
+        return body;
+    }
+    
+    private void removeMootEqualities(PBody body) {
+        Set<Equality> equals = body.getConstraintsOfType(Equality.class);
+        for (Equality equality : equals) {
+            if (equality.isMoot()) {
+                equality.delete();
+                derivativeRemoved(equality, ConstraintRemovalReason.MOOT_EQUALITY);
+            }
+        }
+    }
+
+    /**
+     * Unifies allVariables along equalities so that they can be handled as one.
+     * 
+     * @param body
+     */
+    void unifyVariablesAlongEqualities(PBody body) {
+        Set<Equality> equals = body.getConstraintsOfType(Equality.class);
+        for (Equality equality : equals) {
+            if (!equality.isMoot()) {
+                equality.getWho().unifyInto(equality.getWithWhom());
+            }
+        }
+    }
+
+    /**
+     * Eliminates weak inequalities if they are not substantiated.
+     * 
+     * @param body
+     */
+    void eliminateWeakInequalities(PBody body) {
+        for (Inequality inequality : body.getConstraintsOfType(Inequality.class)){
+            if (inequality.isEliminable()){
+                inequality.eliminateWeak();
+                derivativeRemoved(inequality, ConstraintRemovalReason.WEAK_INEQUALITY_SELF_LOOP);
+            }
+        }
+    }
+
+    /**
+     * Eliminates all type constraints that are inferrable from other constraints.
+     */
+    void eliminateInferrableTypes(final PBody body, IQueryMetaContext context) {
+        Set<TypeJudgement> subsumedByRetainedConstraints = new HashSet<TypeJudgement>();
+        LinkedList<ITypeConstraint> allTypeConstraints = new LinkedList<ITypeConstraint>();
+        for (PConstraint pConstraint : body.getConstraints()) {
+            if (pConstraint instanceof ITypeConstraint) {
+                allTypeConstraints.add((ITypeConstraint) pConstraint);
+            } else if (pConstraint instanceof ITypeInfoProviderConstraint) {
+                // non-type constraints are all retained
+                final Set<TypeJudgement> directJudgements = ((ITypeInfoProviderConstraint) pConstraint)
+                        .getImpliedJudgements(context);
+                subsumedByRetainedConstraints = TypeHelper.typeClosure(subsumedByRetainedConstraints, directJudgements,
+                        context);
+            }
+        }
+        Comparator<ITypeConstraint> eliminationOrder = (o1, o2) -> {
+            IInputKey type1 = o1.getEquivalentJudgement().getInputKey();
+            IInputKey type2 = o2.getEquivalentJudgement().getInputKey();
+            
+            int result = context.getSuggestedEliminationOrdering().compare(type1, type2);
+            return (result == 0) 
+                    ? PConstraint.COMPARE_BY_MONOTONOUS_ID.compare(o1, o2) 
+                    : result;
+        }; 
+                
+        Collections.sort(allTypeConstraints, eliminationOrder);
+        Queue<ITypeConstraint> potentialConstraints = allTypeConstraints; // rename for better comprehension
+
+        while (!potentialConstraints.isEmpty()) {
+            ITypeConstraint candidate = potentialConstraints.poll();
+
+            boolean isSubsumed = subsumedByRetainedConstraints.contains(candidate.getEquivalentJudgement());
+            if (!isSubsumed) {
+                Set<TypeJudgement> typeClosure = subsumedByRetainedConstraints;
+                for (ITypeConstraint subsuming : potentialConstraints) { // the remaining ones
+                    final Set<TypeJudgement> directJudgements = subsuming.getImpliedJudgements(context);
+                    typeClosure = TypeHelper.typeClosure(typeClosure, directJudgements, context);
+
+                    if (typeClosure.contains(candidate.getEquivalentJudgement())) {
+                        isSubsumed = true;
+                        break;
+                    }
+                }
+            }
+            if (isSubsumed) { // eliminated
+                candidate.delete();
+                derivativeRemoved(candidate, ConstraintRemovalReason.TYPE_SUBSUMED);
+            } else { // retained
+                subsumedByRetainedConstraints = TypeHelper.typeClosure(subsumedByRetainedConstraints,
+                        candidate.getImpliedJudgements(context), context);
+            }
+        }
+    }
+
+    /**
+     * Inserts "weakened alternative" constraints suggested by the meta context that aid in coming up with a query plan.
+     */
+    void expandWeakenedAlternativeConstraints(PBody body) {
+        Set<TypeJudgement> allJudgements = new HashSet<TypeJudgement>();
+        Set<TypeJudgement> newJudgementsToAdd = new HashSet<TypeJudgement>();
+        Queue<TypeJudgement> judgementsToProcess = new LinkedList<TypeJudgement>();
+        Map<TypeJudgement, List<PConstraint>> traceability = CollectionsFactory.createMap();
+        
+        for (ITypeConstraint typeConstraint : body.getConstraintsOfType(ITypeConstraint.class)) {
+            TypeJudgement equivalentJudgement = typeConstraint.getEquivalentJudgement();
+            judgementsToProcess.add(equivalentJudgement);
+            allJudgements.add(equivalentJudgement);
+            traceability.computeIfAbsent(equivalentJudgement, k-> new ArrayList<>()).add(typeConstraint);
+        }
+        
+        while (!judgementsToProcess.isEmpty()) {
+            TypeJudgement judgement = judgementsToProcess.poll();
+            for (TypeJudgement alternativeJudgement : judgement.getWeakenedAlternativeJudgements(context)) {
+                if (allJudgements.add(alternativeJudgement)) {
+                    newJudgementsToAdd.add(alternativeJudgement);
+                    judgementsToProcess.add(alternativeJudgement);
+                    traceability.merge(
+                            alternativeJudgement, 
+                            traceability.getOrDefault(judgement, new ArrayList<>()),
+                            (old,further) -> {old.addAll(further); return old;}
+                    );
+                }
+            }
+        }
+        
+        for (TypeJudgement typeJudgement : newJudgementsToAdd) {
+            PConstraint newConstraint = typeJudgement.createConstraintFor(body);
+            for (PConstraint source : traceability.getOrDefault(typeJudgement, Collections.emptyList())) {
+                addTrace(source, newConstraint);
+            }
+        }        
+    }
+    
+    private Object getConstraintKey(PConstraint constraint) {
+        if (constraint instanceof ITypeConstraint) {
+            return ((ITypeConstraint) constraint).getEquivalentJudgement();
+        }
+        // Do not check duplication for any other types
+        return constraint;
+    }
+    
+    void eliminateDuplicateTypeConstraints(PBody body) {
+        Map<Object, PConstraint> constraints = new HashMap<>();
+        for (PConstraint constraint : body.getConstraints()) {
+            Object key = getConstraintKey(constraint);
+            // Retain first found instance of a constraint
+            if (!constraints.containsKey(key)) {
+                constraints.put(key, constraint);
+            }
+        }
+
+        // Retain collected constraints, remove everything else
+        Iterator<PConstraint> iterator = body.getConstraints().iterator();
+        Collection<PConstraint> toRetain = constraints.values(); 
+        while(iterator.hasNext()){
+            PConstraint next = iterator.next();
+            if (!toRetain.contains(next)){
+                derivativeRemoved(next, ConstraintRemovalReason.DUPLICATE);
+                iterator.remove();
+            }
+        }
+    }
+    
+    /**
+     * Verifies the sanity of all constraints. Should be issued as a preventive check before layouting.
+     * 
+     * @param body
+     * @throws RetePatternBuildException
+     */
+    void checkSanity(PBody body) {
+        for (PConstraint pConstraint : body.getConstraints())
+            pConstraint.checkSanity();
+    }
+
+}