From 7f2df1ba80aac7e1c5e99315bf5a8e32ad7456da Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Fri, 21 Jul 2023 02:18:06 +0200 Subject: feat: custom connected component RETE node --- .../rete/network/RefineryConnectionFactory.java | 34 +++ .../runtime/rete/network/RefineryNodeFactory.java | 37 ++++ .../internal/ViatraModelQueryBuilderImpl.java | 6 +- .../query/viatra/internal/pquery/Dnf2PQuery.java | 34 ++- .../pquery/RepresentativeElectionConstraint.java | 45 ++++ .../pquery/rewriter/RefineryPBodyCopier.java | 35 ++++ .../pquery/rewriter/RefineryPBodyNormalizer.java | 38 ++++ .../rewriter/RefinerySurrogateQueryRewriter.java | 58 ++++++ .../internal/rete/RefineryReteBackendFactory.java | 90 ++++++++ .../viatra/internal/rete/RefineryReteEngine.java | 134 ++++++++++++ .../internal/rete/RefineryReteRecipeCompiler.java | 228 +++++++++++++++++++++ .../RefineryConnectionFactoryExtensions.java | 47 +++++ .../network/RefineryNodeFactoryExtensions.java | 44 ++++ .../network/RepresentativeElectionAlgorithm.java | 137 +++++++++++++ .../rete/network/RepresentativeElectionNode.java | 120 +++++++++++ .../StronglyConnectedComponentAlgorithm.java | 66 ++++++ .../network/WeaklyConnectedComponentAlgorithm.java | 85 ++++++++ .../rete/recipe/RefineryRecipesFactory.java | 22 ++ .../rete/recipe/RefineryRecipesFactoryImpl.java | 74 +++++++ .../rete/recipe/RefineryRecipesPackage.java | 41 ++++ .../rete/recipe/RefineryRecipesPackageImpl.java | 96 +++++++++ .../rete/recipe/RepresentativeElectionRecipe.java | 17 ++ .../recipe/RepresentativeElectionRecipeImpl.java | 105 ++++++++++ .../viatra/StronglyConnectedComponentsTest.java | 217 ++++++++++++++++++++ .../viatra/WeaklyConnectedComponentsTest.java | 188 +++++++++++++++++ .../refinery/store/query/literal/CallLiteral.java | 4 + .../refinery/store/query/literal/Connectivity.java | 18 ++ .../literal/RepresentativeElectionLiteral.java | 102 +++++++++ .../store/reasoning/lifting/ClauseLifter.java | 2 + .../store/reasoning/lifting/DnfLifter.java | 2 +- 30 files changed, 2112 insertions(+), 14 deletions(-) create mode 100644 subprojects/store-query-viatra/src/main/java/org/eclipse/viatra/query/runtime/rete/network/RefineryConnectionFactory.java create mode 100644 subprojects/store-query-viatra/src/main/java/org/eclipse/viatra/query/runtime/rete/network/RefineryNodeFactory.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/RepresentativeElectionConstraint.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/rewriter/RefineryPBodyCopier.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/rewriter/RefineryPBodyNormalizer.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/rewriter/RefinerySurrogateQueryRewriter.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/RefineryReteBackendFactory.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/RefineryReteEngine.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/RefineryReteRecipeCompiler.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RefineryConnectionFactoryExtensions.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RefineryNodeFactoryExtensions.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RepresentativeElectionAlgorithm.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RepresentativeElectionNode.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/StronglyConnectedComponentAlgorithm.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/WeaklyConnectedComponentAlgorithm.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesFactory.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesFactoryImpl.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesPackage.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesPackageImpl.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RepresentativeElectionRecipe.java create mode 100644 subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RepresentativeElectionRecipeImpl.java create mode 100644 subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/StronglyConnectedComponentsTest.java create mode 100644 subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/WeaklyConnectedComponentsTest.java create mode 100644 subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Connectivity.java create mode 100644 subprojects/store-query/src/main/java/tools/refinery/store/query/literal/RepresentativeElectionLiteral.java (limited to 'subprojects') diff --git a/subprojects/store-query-viatra/src/main/java/org/eclipse/viatra/query/runtime/rete/network/RefineryConnectionFactory.java b/subprojects/store-query-viatra/src/main/java/org/eclipse/viatra/query/runtime/rete/network/RefineryConnectionFactory.java new file mode 100644 index 00000000..241c5b58 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/org/eclipse/viatra/query/runtime/rete/network/RefineryConnectionFactory.java @@ -0,0 +1,34 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package org.eclipse.viatra.query.runtime.rete.network; + +import org.eclipse.viatra.query.runtime.rete.traceability.RecipeTraceInfo; +import tools.refinery.store.query.viatra.internal.rete.network.RefineryConnectionFactoryExtensions; + +/** + * This class overrides some RETE connection types from {@link ConnectionFactory}. + *

+ * Since {@link ConnectionFactory} is package-private, this class has to be in the + * {@code org.eclipse.viatra.query.runtime.rete.network} package as well. + * However, due to JAR signature verification errors, this class cannot be loaded directly + * and has to be loaded at runtime as a byte array instead. + */ +@SuppressWarnings("unused") +public class RefineryConnectionFactory extends ConnectionFactory { + private final RefineryConnectionFactoryExtensions extensions; + + public RefineryConnectionFactory(ReteContainer reteContainer) { + super(reteContainer); + extensions = new RefineryConnectionFactoryExtensions(reteContainer); + } + + @Override + public void connectToParents(RecipeTraceInfo recipeTrace, Node freshNode) { + if (!extensions.connectToParents(recipeTrace, freshNode)) { + super.connectToParents(recipeTrace, freshNode); + } + } +} diff --git a/subprojects/store-query-viatra/src/main/java/org/eclipse/viatra/query/runtime/rete/network/RefineryNodeFactory.java b/subprojects/store-query-viatra/src/main/java/org/eclipse/viatra/query/runtime/rete/network/RefineryNodeFactory.java new file mode 100644 index 00000000..1a76e22a --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/org/eclipse/viatra/query/runtime/rete/network/RefineryNodeFactory.java @@ -0,0 +1,37 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package org.eclipse.viatra.query.runtime.rete.network; + +import org.apache.log4j.Logger; +import org.eclipse.viatra.query.runtime.rete.recipes.ReteNodeRecipe; +import org.eclipse.viatra.query.runtime.rete.traceability.TraceInfo; +import tools.refinery.store.query.viatra.internal.rete.network.RefineryNodeFactoryExtensions; + +/** + * This class overrides some RETE node types from {@link NodeFactory}. + *

+ * Since {@link NodeFactory} is package-private, this class has to be in the + * {@code org.eclipse.viatra.query.runtime.rete.network} package as well. + * However, due to JAR signature verification errors, this class cannot be loaded directly + * and has to be loaded at runtime as a byte array instead. + */ +@SuppressWarnings("unused") +class RefineryNodeFactory extends NodeFactory { + private final RefineryNodeFactoryExtensions extensions = new RefineryNodeFactoryExtensions(); + + public RefineryNodeFactory(Logger logger) { + super(logger); + } + + @Override + public Supplier createNode(ReteContainer reteContainer, ReteNodeRecipe recipe, TraceInfo... traces) { + var extendedResult = extensions.createNode(reteContainer, recipe, traces); + if (extendedResult != null) { + return extendedResult; + } + return super.createNode(reteContainer, recipe, traces); + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryBuilderImpl.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryBuilderImpl.java index 5ee8bd74..bf0708bf 100644 --- a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryBuilderImpl.java +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/ViatraModelQueryBuilderImpl.java @@ -10,7 +10,6 @@ import org.eclipse.viatra.query.runtime.api.ViatraQueryEngineOptions; import org.eclipse.viatra.query.runtime.localsearch.matcher.integration.LocalSearchHintOptions; import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendFactory; import org.eclipse.viatra.query.runtime.matchers.backend.QueryEvaluationHint; -import org.eclipse.viatra.query.runtime.rete.matcher.ReteBackendFactory; import tools.refinery.store.adapter.AbstractModelAdapterBuilder; import tools.refinery.store.model.ModelStore; import tools.refinery.store.query.dnf.AnyQuery; @@ -24,6 +23,7 @@ import tools.refinery.store.query.viatra.internal.localsearch.FlatCostFunction; import tools.refinery.store.query.viatra.internal.localsearch.RelationalLocalSearchBackendFactory; import tools.refinery.store.query.viatra.internal.matcher.RawPatternMatcher; import tools.refinery.store.query.viatra.internal.pquery.Dnf2PQuery; +import tools.refinery.store.query.viatra.internal.rete.RefineryReteBackendFactory; import java.util.*; import java.util.function.Function; @@ -41,8 +41,8 @@ public class ViatraModelQueryBuilderImpl extends AbstractModelAdapterBuilder aggregationLiteral) { translateAggregationLiteral(aggregationLiteral, body); + } else if (literal instanceof RepresentativeElectionLiteral representativeElectionLiteral) { + translateRepresentativeElectionLiteral(representativeElectionLiteral, body); } else { throw new IllegalArgumentException("Unknown literal: " + literal.toString()); } @@ -157,15 +163,7 @@ public class Dnf2PQuery { } case TRANSITIVE -> { var substitution = translateSubstitution(callLiteral.getArguments(), body); - var constraint = callLiteral.getTarget(); - PQuery pattern; - if (constraint instanceof Dnf dnf) { - pattern = translate(dnf); - } else if (constraint instanceof AnySymbolView symbolView) { - pattern = wrapperFactory.wrapSymbolViewIdentityArguments(symbolView); - } else { - throw new IllegalArgumentException("Unknown Constraint: " + constraint); - } + var pattern = wrapConstraintWithIdentityArguments(callLiteral.getTarget()); new BinaryTransitiveClosure(body, substitution, pattern); } case NEGATIVE -> { @@ -178,6 +176,16 @@ public class Dnf2PQuery { } } + private PQuery wrapConstraintWithIdentityArguments(Constraint constraint) { + if (constraint instanceof Dnf dnf) { + return translate(dnf); + } else if (constraint instanceof AnySymbolView symbolView) { + return wrapperFactory.wrapSymbolViewIdentityArguments(symbolView); + } else { + throw new IllegalArgumentException("Unknown Constraint: " + constraint); + } + } + private static Tuple translateSubstitution(List substitution, PBody body) { int arity = substitution.size(); Object[] variables = new Object[arity]; @@ -240,4 +248,10 @@ public class Dnf2PQuery { new AggregatorConstraint(boundAggregator, body, substitution, wrappedCall.pattern(), resultVariable, aggregatedColumn); } + + private void translateRepresentativeElectionLiteral(RepresentativeElectionLiteral literal, PBody body) { + var substitution = translateSubstitution(literal.getArguments(), body); + var pattern = wrapConstraintWithIdentityArguments(literal.getTarget()); + new RepresentativeElectionConstraint(body, substitution, pattern, literal.getConnectivity()); + } } diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/RepresentativeElectionConstraint.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/RepresentativeElectionConstraint.java new file mode 100644 index 00000000..e146213e --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/RepresentativeElectionConstraint.java @@ -0,0 +1,45 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.pquery; + +import org.eclipse.viatra.query.runtime.matchers.context.IQueryMetaContext; +import org.eclipse.viatra.query.runtime.matchers.psystem.*; +import org.eclipse.viatra.query.runtime.matchers.psystem.basicenumerables.PositivePatternCall; +import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PQuery; +import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple; +import tools.refinery.store.query.literal.Connectivity; + +import java.util.Set; + +public class RepresentativeElectionConstraint extends KeyedEnumerablePConstraint + implements IQueryReference, ITypeInfoProviderConstraint { + private final Connectivity connectivity; + + public RepresentativeElectionConstraint(PBody pBody, Tuple variablesTuple, PQuery supplierKey, + Connectivity connectivity) { + super(pBody, variablesTuple, supplierKey); + this.connectivity = connectivity; + } + + public Connectivity getConnectivity() { + return connectivity; + } + + @Override + public PQuery getReferredQuery() { + return supplierKey; + } + + @Override + public Set getImpliedJudgements(IQueryMetaContext context) { + return PositivePatternCall.getTypesImpliedByCall(supplierKey, variablesTuple); + } + + @Override + protected String keyToString() { + return supplierKey.getFullyQualifiedName() + "#representative"; + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/rewriter/RefineryPBodyCopier.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/rewriter/RefineryPBodyCopier.java new file mode 100644 index 00000000..a833a37b --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/rewriter/RefineryPBodyCopier.java @@ -0,0 +1,35 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.pquery.rewriter; + +import org.eclipse.viatra.query.runtime.matchers.psystem.PBody; +import org.eclipse.viatra.query.runtime.matchers.psystem.PConstraint; +import org.eclipse.viatra.query.runtime.matchers.psystem.rewriters.IRewriterTraceCollector; +import org.eclipse.viatra.query.runtime.matchers.psystem.rewriters.PBodyCopier; +import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples; +import tools.refinery.store.query.viatra.internal.pquery.RepresentativeElectionConstraint; + +public class RefineryPBodyCopier extends PBodyCopier { + public RefineryPBodyCopier(PBody body, IRewriterTraceCollector traceCollector) { + super(body, traceCollector); + } + + @Override + protected void copyConstraint(PConstraint constraint) { + if (constraint instanceof RepresentativeElectionConstraint representativeElectionConstraint) { + copyRepresentativeElectionConstraint(representativeElectionConstraint); + } else { + super.copyConstraint(constraint); + } + } + + private void copyRepresentativeElectionConstraint(RepresentativeElectionConstraint constraint) { + var mappedVariables = extractMappedVariables(constraint); + var variablesTuple = Tuples.flatTupleOf((Object[]) mappedVariables); + addTrace(constraint, new RepresentativeElectionConstraint(body, variablesTuple, constraint.getReferredQuery(), + constraint.getConnectivity())); + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/rewriter/RefineryPBodyNormalizer.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/rewriter/RefineryPBodyNormalizer.java new file mode 100644 index 00000000..ed85a843 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/rewriter/RefineryPBodyNormalizer.java @@ -0,0 +1,38 @@ +/******************************************************************************* + * Copyright (c) 2004-2010 Gabor Bergmann and Daniel Varro + * Copyright (c) 2023 The Refinery Authors + * 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.store.query.viatra.internal.pquery.rewriter; + +import org.eclipse.viatra.query.runtime.matchers.context.IQueryMetaContext; +import org.eclipse.viatra.query.runtime.matchers.psystem.PBody; +import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PDisjunction; +import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PQuery; +import org.eclipse.viatra.query.runtime.matchers.psystem.rewriters.PBodyCopier; +import org.eclipse.viatra.query.runtime.matchers.psystem.rewriters.PBodyNormalizer; + +import java.util.LinkedHashSet; +import java.util.Set; + +public class RefineryPBodyNormalizer extends PBodyNormalizer { + public RefineryPBodyNormalizer(IQueryMetaContext context) { + super(context); + } + + @Override + public PDisjunction rewrite(PDisjunction disjunction) { + Set normalizedBodies = new LinkedHashSet<>(); + for (PBody body : disjunction.getBodies()) { + PBodyCopier copier = new RefineryPBodyCopier(body, getTraceCollector()); + PBody modifiedBody = copier.getCopiedBody(); + normalizeBody(modifiedBody); + normalizedBodies.add(modifiedBody); + modifiedBody.setStatus(PQuery.PQueryStatus.OK); + } + return new PDisjunction(normalizedBodies); + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/rewriter/RefinerySurrogateQueryRewriter.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/rewriter/RefinerySurrogateQueryRewriter.java new file mode 100644 index 00000000..dc288ba0 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/pquery/rewriter/RefinerySurrogateQueryRewriter.java @@ -0,0 +1,58 @@ +/******************************************************************************* + * Copyright (c) 2010-2015, Zoltan Ujhelyi, Istvan Rath and Daniel Varro + * Copyright (c) 2023 The Refinery Authors + * 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.store.query.viatra.internal.pquery.rewriter; + +import org.eclipse.viatra.query.runtime.matchers.context.IInputKey; +import org.eclipse.viatra.query.runtime.matchers.context.surrogate.SurrogateQueryRegistry; +import org.eclipse.viatra.query.runtime.matchers.psystem.PBody; +import org.eclipse.viatra.query.runtime.matchers.psystem.PVariable; +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.PDisjunction; +import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PQuery; +import org.eclipse.viatra.query.runtime.matchers.psystem.rewriters.PBodyCopier; +import org.eclipse.viatra.query.runtime.matchers.psystem.rewriters.PDisjunctionRewriter; +import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple; +import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples; + +import java.util.LinkedHashSet; +import java.util.Set; + +public class RefinerySurrogateQueryRewriter extends PDisjunctionRewriter { + @Override + public PDisjunction rewrite(PDisjunction disjunction) { + Set replacedBodies = new LinkedHashSet<>(); + for (PBody body : disjunction.getBodies()) { + PBodyCopier copier = new RefineryPBodyCopier(body, getTraceCollector()) { + + @Override + protected void copyTypeConstraint(TypeConstraint typeConstraint) { + PVariable[] mappedVariables = extractMappedVariables(typeConstraint); + Tuple variablesTuple = Tuples.flatTupleOf((Object[]) mappedVariables); + final IInputKey supplierKey = typeConstraint.getSupplierKey(); + if (SurrogateQueryRegistry.instance().hasSurrogateQueryFQN(supplierKey)) { + PQuery surrogateQuery = SurrogateQueryRegistry.instance().getSurrogateQuery(supplierKey); + if (surrogateQuery == null) { + throw new IllegalStateException("Surrogate query for feature %s not found" + .formatted(supplierKey.getPrettyPrintableName())); + } + addTrace(typeConstraint, new PositivePatternCall(getCopiedBody(), variablesTuple, + surrogateQuery)); + } else { + addTrace(typeConstraint, new TypeConstraint(getCopiedBody(), variablesTuple, supplierKey)); + } + } + }; + PBody modifiedBody = copier.getCopiedBody(); + replacedBodies.add(modifiedBody); + modifiedBody.setStatus(PQuery.PQueryStatus.OK); + } + return new PDisjunction(replacedBodies); + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/RefineryReteBackendFactory.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/RefineryReteBackendFactory.java new file mode 100644 index 00000000..517e511a --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/RefineryReteBackendFactory.java @@ -0,0 +1,90 @@ +/******************************************************************************* + * Copyright (c) 2010-2014, Bergmann Gabor, Istvan Rath and Daniel Varro + * Copyright (c) 2023 The Refinery Authors + * 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.store.query.viatra.internal.rete; + +import org.eclipse.viatra.query.runtime.matchers.backend.*; +import org.eclipse.viatra.query.runtime.matchers.context.IQueryBackendContext; +import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PQuery; +import org.eclipse.viatra.query.runtime.rete.construction.plancompiler.ReteRecipeCompiler; +import org.eclipse.viatra.query.runtime.rete.matcher.IncrementalMatcherCapability; +import org.eclipse.viatra.query.runtime.rete.matcher.ReteEngine; +import org.eclipse.viatra.query.runtime.rete.matcher.TimelyConfiguration; +import org.eclipse.viatra.query.runtime.rete.util.Options; + +// Singleton implementations follows the VIATRA implementation. +@SuppressWarnings("squid:S6548") +public class RefineryReteBackendFactory implements IQueryBackendFactory { + /** + * EXPERIMENTAL + */ + protected static final int RETE_THREADS = 0; + + /** + * @since 2.0 + */ + public static final RefineryReteBackendFactory INSTANCE = new RefineryReteBackendFactory(); + + /** + * @since 1.5 + */ + @Override + public IQueryBackend create(IQueryBackendContext context) { + return create(context, false, null); + } + + /** + * @since 2.4 + */ + public IQueryBackend create(IQueryBackendContext context, boolean deleteAndReDeriveEvaluation, + TimelyConfiguration timelyConfiguration) { + ReteEngine engine; + engine = new RefineryReteEngine(context, RETE_THREADS, deleteAndReDeriveEvaluation, timelyConfiguration); + IQueryBackendHintProvider hintConfiguration = engine.getHintConfiguration(); + ReteRecipeCompiler compiler = new RefineryReteRecipeCompiler( + Options.builderMethod.layoutStrategy(context, hintConfiguration), context.getLogger(), + context.getRuntimeContext().getMetaContext(), context.getQueryCacheContext(), hintConfiguration, + context.getQueryAnalyzer(), deleteAndReDeriveEvaluation, timelyConfiguration); + engine.setCompiler(compiler); + return engine; + } + + @Override + public Class getBackendClass() { + return ReteEngine.class; + } + + @Override + public int hashCode() { + return RefineryReteBackendFactory.class.hashCode(); + } + + @Override + public boolean equals(Object obj) { + if (this == obj) { + return true; + } + if (obj == null) { + return false; + } + return obj instanceof RefineryReteBackendFactory; + } + + /** + * @since 1.4 + */ + @Override + public IMatcherCapability calculateRequiredCapability(PQuery query, QueryEvaluationHint hint) { + return new IncrementalMatcherCapability(); + } + + @Override + public boolean isCaching() { + return true; + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/RefineryReteEngine.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/RefineryReteEngine.java new file mode 100644 index 00000000..c088219b --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/RefineryReteEngine.java @@ -0,0 +1,134 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.rete; + +import org.apache.log4j.Logger; +import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendFactory; +import org.eclipse.viatra.query.runtime.matchers.context.IQueryBackendContext; +import org.eclipse.viatra.query.runtime.rete.matcher.ReteEngine; +import org.eclipse.viatra.query.runtime.rete.matcher.TimelyConfiguration; +import org.eclipse.viatra.query.runtime.rete.network.Network; +import org.eclipse.viatra.query.runtime.rete.network.NodeProvisioner; +import org.eclipse.viatra.query.runtime.rete.network.ReteContainer; + +import java.io.IOException; +import java.lang.invoke.MethodHandle; +import java.lang.invoke.MethodHandles; +import java.lang.invoke.MethodType; + +public class RefineryReteEngine extends ReteEngine { + private static final MethodHandle REFINERY_NODE_FACTORY_CONSTRUCTOR; + private static final MethodHandle REFINERY_CONNECTION_FACTORY_CONSTRUCTOR; + private static final MethodHandle NETWORK_NODE_FACTORY_SETTER; + private static final MethodHandle RETE_CONTAINER_CONNECTION_FACTORY_SETTER; + private static final MethodHandle NODE_PROVISIONER_NODE_FACTORY_SETTER; + private static final MethodHandle NODE_PROVISIONER_CONNECTION_FACTORY_SETTER; + + static { + MethodHandles.Lookup lookup; + try { + lookup = MethodHandles.privateLookupIn(Network.class, MethodHandles.lookup()); + } catch (IllegalAccessException e) { + throw new IllegalStateException("Cannot create private lookup", e); + } + var refineryNodeFactoryClass = defineClassFromFile(lookup, "RefineryNodeFactory"); + var refinaryConnectionFactoryClass = defineClassFromFile(lookup, "RefineryConnectionFactory"); + try { + REFINERY_NODE_FACTORY_CONSTRUCTOR = lookup.findConstructor(refineryNodeFactoryClass, + MethodType.methodType(Void.TYPE, Logger.class)); + REFINERY_CONNECTION_FACTORY_CONSTRUCTOR = lookup.findConstructor(refinaryConnectionFactoryClass, + MethodType.methodType(Void.TYPE, ReteContainer.class)); + } catch (NoSuchMethodException | IllegalAccessException e) { + throw new IllegalStateException("Cannot get constructor", e); + } + var nodeFactoryClass = refineryNodeFactoryClass.getSuperclass(); + var connectionFactoryClass = refinaryConnectionFactoryClass.getSuperclass(); + try { + NETWORK_NODE_FACTORY_SETTER = lookup.findSetter(Network.class, "nodeFactory", nodeFactoryClass); + RETE_CONTAINER_CONNECTION_FACTORY_SETTER = lookup.findSetter(ReteContainer.class, "connectionFactory", + connectionFactoryClass); + NODE_PROVISIONER_NODE_FACTORY_SETTER = lookup.findSetter(NodeProvisioner.class, "nodeFactory", + nodeFactoryClass); + NODE_PROVISIONER_CONNECTION_FACTORY_SETTER = lookup.findSetter(NodeProvisioner.class, "connectionFactory", + connectionFactoryClass); + } catch (NoSuchFieldException | IllegalAccessException e) { + throw new IllegalStateException("Cannot get field setter", e); + } + } + + private static Class defineClassFromFile(MethodHandles.Lookup lookup, String name) { + byte[] classBytes; + try (var resource = Network.class.getResourceAsStream(name + ".class")) { + if (resource == null) { + throw new IllegalStateException("Cannot find %s class file".formatted(name)); + } + classBytes = resource.readAllBytes(); + } catch (IOException e) { + throw new IllegalStateException("Cannot read %s class file".formatted(name), e); + } + Class clazz; + try { + clazz = lookup.defineClass(classBytes); + } catch (IllegalAccessException e) { + throw new IllegalStateException("Cannot define %s class".formatted(name), e); + } + return clazz; + } + + public RefineryReteEngine(IQueryBackendContext context, int reteThreads, boolean deleteAndReDeriveEvaluation, + TimelyConfiguration timelyConfiguration) { + super(context, reteThreads, deleteAndReDeriveEvaluation, timelyConfiguration); + installFactories(); + } + + private void installFactories() { + var logger = getLogger(); + Object nodeFactory; + try { + nodeFactory = REFINERY_NODE_FACTORY_CONSTRUCTOR.invoke(logger); + } catch (Error e) { + // Fatal JVM errors should not be wrapped. + throw e; + } catch (Throwable e) { + throw new IllegalStateException("Cannot construct node factory", e); + } + try { + NETWORK_NODE_FACTORY_SETTER.invoke(reteNet, nodeFactory); + } catch (Error e) { + // Fatal JVM errors should not be wrapped. + throw e; + } catch (Throwable e) { + throw new IllegalStateException("Cannot set factory", e); + } + for (var container : reteNet.getContainers()) { + Object connectionFactory; + try { + connectionFactory = REFINERY_CONNECTION_FACTORY_CONSTRUCTOR.invoke(container); + } catch (Error e) { + // Fatal JVM errors should not be wrapped. + throw e; + } catch (Throwable e) { + throw new IllegalStateException("Cannot construct connection factory", e); + } + var provisioner = container.getProvisioner(); + try { + RETE_CONTAINER_CONNECTION_FACTORY_SETTER.invoke(container, connectionFactory); + NODE_PROVISIONER_NODE_FACTORY_SETTER.invoke(provisioner, nodeFactory); + NODE_PROVISIONER_CONNECTION_FACTORY_SETTER.invoke(provisioner, connectionFactory); + } catch (Error e) { + // Fatal JVM errors should not be wrapped. + throw e; + } catch (Throwable e) { + throw new IllegalStateException("Cannot set factory", e); + } + } + } + + @Override + public IQueryBackendFactory getFactory() { + return RefineryReteBackendFactory.INSTANCE; + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/RefineryReteRecipeCompiler.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/RefineryReteRecipeCompiler.java new file mode 100644 index 00000000..fd1b48d8 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/RefineryReteRecipeCompiler.java @@ -0,0 +1,228 @@ +/******************************************************************************* + * Copyright (c) 2010-2014, Bergmann Gabor, Istvan Rath and Daniel Varro + * Copyright (c) 2023 The Refinery Authors + * 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.store.query.viatra.internal.rete; + +import org.apache.log4j.Logger; +import org.eclipse.viatra.query.runtime.matchers.backend.IQueryBackendHintProvider; +import org.eclipse.viatra.query.runtime.matchers.context.IQueryCacheContext; +import org.eclipse.viatra.query.runtime.matchers.context.IQueryMetaContext; +import org.eclipse.viatra.query.runtime.matchers.planning.IQueryPlannerStrategy; +import org.eclipse.viatra.query.runtime.matchers.planning.SubPlan; +import org.eclipse.viatra.query.runtime.matchers.planning.operations.PApply; +import org.eclipse.viatra.query.runtime.matchers.planning.operations.PEnumerate; +import org.eclipse.viatra.query.runtime.matchers.psystem.EnumerablePConstraint; +import org.eclipse.viatra.query.runtime.matchers.psystem.analysis.QueryAnalyzer; +import org.eclipse.viatra.query.runtime.matchers.psystem.queries.PQuery; +import org.eclipse.viatra.query.runtime.matchers.psystem.rewriters.PDisjunctionRewriterCacher; +import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple; +import org.eclipse.viatra.query.runtime.rete.construction.plancompiler.CompilerHelper; +import org.eclipse.viatra.query.runtime.rete.construction.plancompiler.ReteRecipeCompiler; +import org.eclipse.viatra.query.runtime.rete.matcher.TimelyConfiguration; +import org.eclipse.viatra.query.runtime.rete.recipes.ReteNodeRecipe; +import org.eclipse.viatra.query.runtime.rete.traceability.CompiledSubPlan; +import org.eclipse.viatra.query.runtime.rete.traceability.PlanningTrace; +import org.eclipse.viatra.query.runtime.rete.util.ReteHintOptions; +import org.jetbrains.annotations.Nullable; +import tools.refinery.store.query.viatra.internal.pquery.RepresentativeElectionConstraint; +import tools.refinery.store.query.viatra.internal.rete.recipe.RefineryRecipesFactory; +import tools.refinery.store.query.viatra.internal.pquery.rewriter.RefineryPBodyNormalizer; +import tools.refinery.store.query.viatra.internal.pquery.rewriter.RefinerySurrogateQueryRewriter; + +import java.lang.invoke.MethodHandle; +import java.lang.invoke.MethodHandles; +import java.lang.invoke.MethodType; +import java.lang.reflect.Field; +import java.util.Map; + +// Since we don't modify VIATRA code, this is our last resort. +@SuppressWarnings("squid:S3011") +public class RefineryReteRecipeCompiler extends ReteRecipeCompiler { + private static final MethodHandle GET_SUB_PLAN_COMPILER_CACHE; + private static final MethodHandle GET_COMPILER_BACK_TRACE; + private static final Field NORMALIZER_FIELD; + private static final MethodHandle DO_COMPILE_DISPATCH; + private static final MethodHandle COMPILE_TO_NATURAL_JOIN; + private static final MethodHandle REFER_QUERY; + + static { + MethodHandles.Lookup lookup; + try { + lookup = MethodHandles.privateLookupIn(ReteRecipeCompiler.class, MethodHandles.lookup()); + } catch (IllegalAccessException e) { + throw new IllegalStateException("Failed to create lookup", e); + } + try { + GET_SUB_PLAN_COMPILER_CACHE = lookup.findGetter(ReteRecipeCompiler.class, "subPlanCompilerCache", + Map.class); + GET_COMPILER_BACK_TRACE = lookup.findGetter(ReteRecipeCompiler.class, "compilerBackTrace", Map.class); + } catch (NoSuchFieldException | IllegalAccessException e) { + throw new IllegalStateException("Failed to find getter", e); + } + + try { + NORMALIZER_FIELD = ReteRecipeCompiler.class.getDeclaredField("normalizer"); + } catch (NoSuchFieldException e) { + throw new IllegalStateException("Failed to find field", e); + } + NORMALIZER_FIELD.setAccessible(true); + + try { + DO_COMPILE_DISPATCH = lookup.findVirtual(ReteRecipeCompiler.class, "doCompileDispatch", + MethodType.methodType(CompiledSubPlan.class, SubPlan.class)); + COMPILE_TO_NATURAL_JOIN = lookup.findVirtual(ReteRecipeCompiler.class, "compileToNaturalJoin", + MethodType.methodType(CompiledSubPlan.class, SubPlan.class, PlanningTrace.class, + PlanningTrace.class)); + REFER_QUERY = lookup.findVirtual(ReteRecipeCompiler.class, "referQuery", + MethodType.methodType(PlanningTrace.class, PQuery.class, SubPlan.class, Tuple.class)); + } catch (NoSuchMethodException | IllegalAccessException e) { + throw new IllegalStateException("Failed to find method", e); + } + } + + private final Map subPlanCompilerCache; + private final Map compilerBackTrace; + + public RefineryReteRecipeCompiler(IQueryPlannerStrategy plannerStrategy, Logger logger, + IQueryMetaContext metaContext, IQueryCacheContext queryCacheContext, + IQueryBackendHintProvider hintProvider, QueryAnalyzer queryAnalyzer, + boolean deleteAndReDeriveEvaluation, TimelyConfiguration timelyEvaluation) { + super(plannerStrategy, logger, metaContext, queryCacheContext, hintProvider, queryAnalyzer, + deleteAndReDeriveEvaluation, timelyEvaluation); + + var normalizer = new PDisjunctionRewriterCacher(new RefinerySurrogateQueryRewriter(), + new RefineryPBodyNormalizer(metaContext) { + + @Override + protected boolean shouldExpandWeakenedAlternatives(PQuery query) { + var hint = hintProvider.getQueryEvaluationHint(query); + return ReteHintOptions.expandWeakenedAlternativeConstraints.getValueOrDefault(hint); + } + + }); + try { + // https://docs.oracle.com/javase/specs/jls/se17/html/jls-17.html#jls-17.5.3 + // "The object should not be made visible to other threads, nor should the final fields be read, + // until all updates to the final fields of the object are complete." + // The {@code super} constructor only sets but doesn't read the {@code normalizer} field, + // therefore this is fine. + NORMALIZER_FIELD.set(this, normalizer); + } catch (IllegalAccessException e) { + throw new IllegalStateException("Failed to set private final field", e); + } + + try { + @SuppressWarnings("unchecked") + var cache = (Map) GET_SUB_PLAN_COMPILER_CACHE.invokeExact( + (ReteRecipeCompiler) this); + subPlanCompilerCache = cache; + @SuppressWarnings("unchecked") + var backTrace = (Map) GET_COMPILER_BACK_TRACE.invokeExact( + (ReteRecipeCompiler) this); + compilerBackTrace = backTrace; + } catch (Error e) { + // Fatal JVM errors should not be wrapped. + throw e; + } catch (Throwable e) { + throw new IllegalStateException("Failed to access private fields", e); + } + } + + @Override + public CompiledSubPlan getCompiledForm(SubPlan plan) { + CompiledSubPlan compiled = subPlanCompilerCache.get(plan); + if (compiled == null) { + compiled = doCompileDispatchExtension(plan); + if (compiled == null) { + compiled = superDoCompileDispatch(plan); + } + subPlanCompilerCache.put(plan, compiled); + compilerBackTrace.put(compiled.getRecipe(), plan); + } + return compiled; + } + + @Nullable + private CompiledSubPlan doCompileDispatchExtension(SubPlan plan) { + var operation = plan.getOperation(); + if (operation instanceof PEnumerate enumerateOperation) { + return doCompileEnumerateExtension(enumerateOperation.getEnumerablePConstraint(), plan); + } else if (operation instanceof PApply applyOperation && + applyOperation.getPConstraint() instanceof EnumerablePConstraint constraint) { + var secondaryParent = doEnumerateDispatchExtension(plan, constraint); + if (secondaryParent != null) { + var primaryParent = getCompiledForm(plan.getParentPlans().get(0)); + return superCompileToNaturalJoin(plan, primaryParent, secondaryParent); + } + } + return null; + } + + @Nullable + private CompiledSubPlan doCompileEnumerateExtension(EnumerablePConstraint constraint, SubPlan plan) { + var coreTrace = doEnumerateDispatchExtension(plan, constraint); + if (coreTrace == null) { + return null; + } + var trimmedTrace = CompilerHelper.checkAndTrimEqualVariables(plan, coreTrace); + return trimmedTrace.cloneFor(plan); + } + + @Nullable + private PlanningTrace doEnumerateDispatchExtension(SubPlan plan, EnumerablePConstraint constraint) { + if (constraint instanceof RepresentativeElectionConstraint representativeElectionConstraint) { + return compileEnumerableExtension(plan, representativeElectionConstraint); + } + return null; + } + + private PlanningTrace compileEnumerableExtension(SubPlan plan, RepresentativeElectionConstraint constraint) { + var referredQuery = constraint.getSupplierKey(); + var callTrace = superReferQuery(referredQuery, plan, constraint.getVariablesTuple()); + var recipe = RefineryRecipesFactory.eINSTANCE.createRepresentativeElectionRecipe(); + recipe.setParent(callTrace.getRecipe()); + recipe.setConnectivity(constraint.getConnectivity()); + return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), recipe, callTrace); + } + + private CompiledSubPlan superDoCompileDispatch(SubPlan plan) { + try { + return (CompiledSubPlan) DO_COMPILE_DISPATCH.invokeExact((ReteRecipeCompiler) this, plan); + } catch (Error | RuntimeException e) { + // Fatal JVM errors and runtime exceptions should not be wrapped. + throw e; + } catch (Throwable e) { + throw new IllegalStateException("Failed to call doCompileDispatch", e); + } + } + + private CompiledSubPlan superCompileToNaturalJoin(SubPlan plan, PlanningTrace leftCompiled, + PlanningTrace rightCompiled) { + try { + return (CompiledSubPlan) COMPILE_TO_NATURAL_JOIN.invokeExact((ReteRecipeCompiler) this, plan, + leftCompiled, rightCompiled); + } catch (Error | RuntimeException e) { + // Fatal JVM errors and runtime exceptions should not be wrapped. + throw e; + } catch (Throwable e) { + throw new IllegalStateException("Failed to call compileToNaturalJoin", e); + } + } + + private PlanningTrace superReferQuery(PQuery query, SubPlan plan, Tuple actualParametersTuple) { + try { + return (PlanningTrace) REFER_QUERY.invokeExact((ReteRecipeCompiler) this, query, plan, + actualParametersTuple); + } catch (Error | RuntimeException e) { + // Fatal JVM errors and runtime exceptions should not be wrapped. + throw e; + } catch (Throwable e) { + throw new IllegalStateException("Failed to call referQuery", e); + } + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RefineryConnectionFactoryExtensions.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RefineryConnectionFactoryExtensions.java new file mode 100644 index 00000000..0fe5ee27 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RefineryConnectionFactoryExtensions.java @@ -0,0 +1,47 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.rete.network; + +import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple; +import org.eclipse.viatra.query.runtime.rete.network.Node; +import org.eclipse.viatra.query.runtime.rete.network.ReteContainer; +import org.eclipse.viatra.query.runtime.rete.network.Supplier; +import org.eclipse.viatra.query.runtime.rete.remote.Address; +import org.eclipse.viatra.query.runtime.rete.traceability.RecipeTraceInfo; +import tools.refinery.store.query.viatra.internal.rete.recipe.RepresentativeElectionRecipe; + +import java.util.ArrayList; + +public class RefineryConnectionFactoryExtensions { + private final ReteContainer reteContainer; + + public RefineryConnectionFactoryExtensions(ReteContainer reteContainer) { + this.reteContainer = reteContainer; + } + + public boolean connectToParents(RecipeTraceInfo recipeTrace, Node freshNode) { + var recipe = recipeTrace.getRecipe(); + if (recipe instanceof RepresentativeElectionRecipe representativeElectionRecipe) { + connectToParents(representativeElectionRecipe, (RepresentativeElectionNode) freshNode); + return true; + } + return false; + } + + private void connectToParents(RepresentativeElectionRecipe recipe, RepresentativeElectionNode freshNode) { + var parentRecipe = recipe.getParent(); + // Apparently VIATRA ensures that this cast is safe, see + // {@link org.eclipse.viatra.query.runtime.rete.network.ConnectionFactory.connectToParent}. + @SuppressWarnings("unchecked") + var parentAddress = (Address) reteContainer.getNetwork() + .getExistingNodeByRecipe(parentRecipe); + var parentSupplier = reteContainer.getProvisioner().asSupplier(parentAddress); + var tuples = new ArrayList(); + parentSupplier.pullInto(tuples, true); + freshNode.reinitializeWith(tuples); + reteContainer.connect(parentSupplier, freshNode); + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RefineryNodeFactoryExtensions.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RefineryNodeFactoryExtensions.java new file mode 100644 index 00000000..82b63a55 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RefineryNodeFactoryExtensions.java @@ -0,0 +1,44 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.rete.network; + +import org.eclipse.viatra.query.runtime.rete.network.ReteContainer; +import org.eclipse.viatra.query.runtime.rete.network.Supplier; +import org.eclipse.viatra.query.runtime.rete.recipes.ReteNodeRecipe; +import org.eclipse.viatra.query.runtime.rete.traceability.TraceInfo; +import org.jetbrains.annotations.Nullable; +import tools.refinery.store.query.viatra.internal.rete.recipe.RepresentativeElectionRecipe; + +public class RefineryNodeFactoryExtensions { + @Nullable + public Supplier createNode(ReteContainer reteContainer, ReteNodeRecipe recipe, TraceInfo... traces) { + var result = instantiateNode(reteContainer, recipe); + if (result == null) { + return null; + } + for (var traceInfo : traces) { + result.assignTraceInfo(traceInfo); + } + return result; + } + + @Nullable + private Supplier instantiateNode(ReteContainer reteContainer, ReteNodeRecipe recipe) { + if (recipe instanceof RepresentativeElectionRecipe representativeElectionRecipe) { + return instantiateRepresentativeElectionNode(reteContainer, representativeElectionRecipe); + } + return null; + } + + private Supplier instantiateRepresentativeElectionNode(ReteContainer reteContainer, + RepresentativeElectionRecipe recipe) { + RepresentativeElectionAlgorithm.Factory algorithmFactory = switch (recipe.getConnectivity()) { + case STRONG -> StronglyConnectedComponentAlgorithm::new; + case WEAK -> WeaklyConnectedComponentAlgorithm::new; + }; + return new RepresentativeElectionNode(reteContainer, algorithmFactory); + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RepresentativeElectionAlgorithm.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RepresentativeElectionAlgorithm.java new file mode 100644 index 00000000..ff5c7158 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RepresentativeElectionAlgorithm.java @@ -0,0 +1,137 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.rete.network; + +import org.eclipse.viatra.query.runtime.base.itc.graphimpl.Graph; +import org.eclipse.viatra.query.runtime.base.itc.igraph.IGraphObserver; +import org.eclipse.viatra.query.runtime.matchers.util.Direction; + +import java.util.*; + +public abstract class RepresentativeElectionAlgorithm implements IGraphObserver { + protected final Graph graph; + protected final Map representatives = new HashMap<>(); + protected final Map> components = new HashMap<>(); + private RepresentativeElectionNode observer; + + protected RepresentativeElectionAlgorithm(Graph graph) { + this.graph = graph; + initializeComponents(); + graph.attachObserver(this); + } + + protected abstract void initializeComponents(); + + protected void initializeSet(Set set) { + var iterator = set.iterator(); + if (!iterator.hasNext()) { + // Set is empty. + return; + } + var representative = iterator.next(); + for (var node : set) { + var oldRepresentative = representatives.put(node, representative); + if (oldRepresentative != null && !representative.equals(oldRepresentative)) { + throw new IllegalStateException("Node %s is already in a set represented by %s, cannot add it to %s" + .formatted(node, oldRepresentative, set)); + } + } + components.put(representative, set); + } + + protected void merge(Object leftRepresentative, Object rightRepresentative) { + if (leftRepresentative.equals(rightRepresentative)) { + return; + } + var leftSet = getComponent(leftRepresentative); + var rightSet = getComponent(rightRepresentative); + if (leftSet.size() < rightSet.size()) { + merge(rightRepresentative, rightSet, leftRepresentative, leftSet); + } else { + merge(leftRepresentative, leftSet, rightRepresentative, rightSet); + } + } + + private void merge(Object preservedRepresentative, Set preservedSet, Object removedRepresentative, + Set removedSet) { + components.remove(removedRepresentative); + for (var node : removedSet) { + representatives.put(node, preservedRepresentative); + preservedSet.add(node); + notifyToObservers(node, removedRepresentative, preservedRepresentative); + } + } + + protected void assignNewRepresentative(Object oldRepresentative, Set set) { + var iterator = set.iterator(); + if (!iterator.hasNext()) { + return; + } + var newRepresentative = iterator.next(); + components.put(newRepresentative, set); + for (var node : set) { + var oldRepresentativeOfNode = representatives.put(node, newRepresentative); + if (!oldRepresentative.equals(oldRepresentativeOfNode)) { + throw new IllegalArgumentException("Node %s was not represented by %s but by %s" + .formatted(node, oldRepresentative, oldRepresentativeOfNode)); + } + notifyToObservers(node, oldRepresentative, newRepresentative); + } + } + + public void setObserver(RepresentativeElectionNode observer) { + this.observer = observer; + } + + public Map> getComponents() { + return components; + } + + public Object getRepresentative(Object node) { + return representatives.get(node); + } + + public Set getComponent(Object representative) { + return components.get(representative); + } + + public void dispose() { + graph.detachObserver(this); + } + + @Override + public void nodeInserted(Object n) { + var component = new HashSet<>(1); + component.add(n); + initializeSet(component); + notifyToObservers(n, n, Direction.INSERT); + } + + @Override + public void nodeDeleted(Object n) { + var representative = representatives.remove(n); + if (!representative.equals(n)) { + throw new IllegalStateException("Trying to delete node with dangling edges"); + } + components.remove(representative); + notifyToObservers(n, representative, Direction.DELETE); + } + + protected void notifyToObservers(Object node, Object oldRepresentative, Object newRepresentative) { + notifyToObservers(node, oldRepresentative, Direction.DELETE); + notifyToObservers(node, newRepresentative, Direction.INSERT); + } + + protected void notifyToObservers(Object node, Object representative, Direction direction) { + if (observer != null) { + observer.tupleChanged(node, representative, direction); + } + } + + interface Factory { + RepresentativeElectionAlgorithm create(Graph graph); + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RepresentativeElectionNode.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RepresentativeElectionNode.java new file mode 100644 index 00000000..701f6ffe --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/RepresentativeElectionNode.java @@ -0,0 +1,120 @@ +/******************************************************************************* + * Copyright (c) 2010-2012, Tamas Szabo, Gabor Bergmann, Istvan Rath and Daniel Varro + * Copyright (c) 2023 The Refinery Authors + * 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.store.query.viatra.internal.rete.network; + +import org.eclipse.viatra.query.runtime.base.itc.graphimpl.Graph; +import org.eclipse.viatra.query.runtime.matchers.tuple.Tuple; +import org.eclipse.viatra.query.runtime.matchers.tuple.Tuples; +import org.eclipse.viatra.query.runtime.matchers.util.Clearable; +import org.eclipse.viatra.query.runtime.matchers.util.Direction; +import org.eclipse.viatra.query.runtime.matchers.util.timeline.Timeline; +import org.eclipse.viatra.query.runtime.rete.network.ReteContainer; +import org.eclipse.viatra.query.runtime.rete.network.communication.Timestamp; +import org.eclipse.viatra.query.runtime.rete.single.SingleInputNode; + +import java.util.Collection; +import java.util.Map; + +public class RepresentativeElectionNode extends SingleInputNode implements Clearable { + private final RepresentativeElectionAlgorithm.Factory algorithmFactory; + private Graph graph; + private RepresentativeElectionAlgorithm algorithm; + + public RepresentativeElectionNode(ReteContainer reteContainer, + RepresentativeElectionAlgorithm.Factory algorithmFactory) { + super(reteContainer); + this.algorithmFactory = algorithmFactory; + graph = new Graph<>(); + algorithm = algorithmFactory.create(graph); + algorithm.setObserver(this); + reteContainer.registerClearable(this); + } + + @Override + public void networkStructureChanged() { + if (reteContainer.isTimelyEvaluation() && reteContainer.getCommunicationTracker().isInRecursiveGroup(this)) { + throw new IllegalStateException(this + " cannot be used in recursive differential dataflow evaluation!"); + } + super.networkStructureChanged(); + } + + public void reinitializeWith(Collection tuples) { + algorithm.dispose(); + graph = new Graph<>(); + for (var tuple : tuples) { + insertEdge(tuple.get(0), tuple.get(1)); + } + algorithm = algorithmFactory.create(graph); + algorithm.setObserver(this); + } + + public void tupleChanged(Object source, Object representative, Direction direction) { + var tuple = Tuples.staticArityFlatTupleOf(source, representative); + propagateUpdate(direction, tuple, Timestamp.ZERO); + } + + @Override + public void clear() { + algorithm.dispose(); + graph = new Graph<>(); + algorithm = algorithmFactory.create(graph); + } + + @Override + public void update(Direction direction, Tuple updateElement, Timestamp timestamp) { + var source = updateElement.get(0); + var target = updateElement.get(1); + switch (direction) { + case INSERT -> insertEdge(source, target); + case DELETE -> deleteEdge(source, target); + default -> throw new IllegalArgumentException("Unknown direction: " + direction); + } + } + + private void insertEdge(Object source, Object target) { + graph.insertNode(source); + graph.insertNode(target); + graph.insertEdge(source, target); + } + + private void deleteEdge(Object source, Object target) { + graph.deleteEdgeIfExists(source, target); + if (isIsolated(source)) { + graph.deleteNode(source); + } + if (!source.equals(target) && isIsolated(target)) { + graph.deleteNode(target); + } + } + + private boolean isIsolated(Object node) { + return graph.getTargetNodes(node).isEmpty() && graph.getSourceNodes(node).isEmpty(); + } + + @Override + public void pullInto(Collection collector, boolean flush) { + for (var entry : algorithm.getComponents().entrySet()) { + var representative = entry.getKey(); + for (var node : entry.getValue()) { + collector.add(Tuples.staticArityFlatTupleOf(node, representative)); + } + } + } + + @Override + public void pullIntoWithTimeline(Map> collector, boolean flush) { + // Use all zero timestamps because this node cannot be used in recursive groups anyway. + for (var entry : algorithm.getComponents().entrySet()) { + var representative = entry.getKey(); + for (var node : entry.getValue()) { + collector.put(Tuples.staticArityFlatTupleOf(node, representative), Timestamp.INSERT_AT_ZERO_TIMELINE); + } + } + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/StronglyConnectedComponentAlgorithm.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/StronglyConnectedComponentAlgorithm.java new file mode 100644 index 00000000..11155f3e --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/StronglyConnectedComponentAlgorithm.java @@ -0,0 +1,66 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.rete.network; + +import org.eclipse.viatra.query.runtime.base.itc.alg.misc.GraphHelper; +import org.eclipse.viatra.query.runtime.base.itc.alg.misc.bfs.BFS; +import org.eclipse.viatra.query.runtime.base.itc.alg.misc.scc.SCC; +import org.eclipse.viatra.query.runtime.base.itc.graphimpl.Graph; + +import java.util.Collection; +import java.util.Set; + +public class StronglyConnectedComponentAlgorithm extends RepresentativeElectionAlgorithm { + public StronglyConnectedComponentAlgorithm(Graph graph) { + super(graph); + } + + @Override + protected void initializeComponents() { + var computedSCCs = SCC.computeSCC(graph).getSccs(); + for (var computedSCC : computedSCCs) { + initializeSet(computedSCC); + } + } + + @Override + public void edgeInserted(Object source, Object target) { + var sourceRoot = getRepresentative(source); + var targetRoot = getRepresentative(target); + if (sourceRoot.equals(targetRoot)) { + // New edge does not change strongly connected components. + return; + } + if (BFS.isReachable(target, source, graph)) { + merge(sourceRoot, targetRoot); + } + } + + @Override + public void edgeDeleted(Object source, Object target) { + var sourceRoot = getRepresentative(source); + var targetRoot = getRepresentative(target); + if (!sourceRoot.equals(targetRoot)) { + // New edge does not change strongly connected components. + return; + } + var component = GraphHelper.getSubGraph(getComponent(sourceRoot), graph); + if (!BFS.isReachable(source, target, component)) { + var newSCCs = SCC.computeSCC(component).getSccs(); + split(sourceRoot, newSCCs); + } + } + + private void split(Object preservedRepresentative, Collection> sets) { + for (var set : sets) { + if (set.contains(preservedRepresentative)) { + components.put(preservedRepresentative, set); + } else { + assignNewRepresentative(preservedRepresentative, set); + } + } + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/WeaklyConnectedComponentAlgorithm.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/WeaklyConnectedComponentAlgorithm.java new file mode 100644 index 00000000..118004dd --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/network/WeaklyConnectedComponentAlgorithm.java @@ -0,0 +1,85 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.rete.network; + +import org.eclipse.viatra.query.runtime.base.itc.graphimpl.Graph; + +import java.util.ArrayDeque; +import java.util.HashSet; +import java.util.Set; + +public class WeaklyConnectedComponentAlgorithm extends RepresentativeElectionAlgorithm { + public WeaklyConnectedComponentAlgorithm(Graph graph) { + super(graph); + } + + @Override + protected void initializeComponents() { + for (var node : graph.getAllNodes()) { + if (representatives.containsKey(node)) { + continue; + } + var reachable = getReachableNodes(node); + initializeSet(reachable); + } + } + + @Override + public void edgeInserted(Object source, Object target) { + var sourceRoot = getRepresentative(source); + var targetRoot = getRepresentative(target); + merge(sourceRoot, targetRoot); + } + + @Override + public void edgeDeleted(Object source, Object target) { + var sourceRoot = getRepresentative(source); + var targetRoot = getRepresentative(target); + if (!sourceRoot.equals(targetRoot)) { + throw new IllegalArgumentException("Trying to remove edge not in graph"); + } + var targetReachable = getReachableNodes(target); + if (!targetReachable.contains(source)) { + split(sourceRoot, targetReachable); + } + } + + private void split(Object sourceRepresentative, Set targetReachable) { + var sourceComponent = getComponent(sourceRepresentative); + sourceComponent.removeAll(targetReachable); + if (targetReachable.contains(sourceRepresentative)) { + components.put(sourceRepresentative, targetReachable); + assignNewRepresentative(sourceRepresentative, sourceComponent); + } else { + assignNewRepresentative(sourceRepresentative, targetReachable); + } + } + + private Set getReachableNodes(Object source) { + var retSet = new HashSet<>(); + retSet.add(source); + var nodeQueue = new ArrayDeque<>(); + nodeQueue.addLast(source); + + while (!nodeQueue.isEmpty()) { + var node = nodeQueue.removeFirst(); + for (var neighbor : graph.getTargetNodes(node).distinctValues()) { + if (!retSet.contains(neighbor)) { + retSet.add(neighbor); + nodeQueue.addLast(neighbor); + } + } + for (var neighbor : graph.getSourceNodes(node).distinctValues()) { + if (!retSet.contains(neighbor)) { + retSet.add(neighbor); + nodeQueue.addLast(neighbor); + } + } + } + + return retSet; + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesFactory.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesFactory.java new file mode 100644 index 00000000..1f8b3034 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesFactory.java @@ -0,0 +1,22 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.rete.recipe; + +import org.eclipse.emf.ecore.EDataType; +import org.eclipse.emf.ecore.EFactory; +import tools.refinery.store.query.literal.Connectivity; + +// Naming and index computation follows EMF conventions. +@SuppressWarnings("squid:S115") +public interface RefineryRecipesFactory extends EFactory { + RefineryRecipesFactory eINSTANCE = RefineryRecipesFactoryImpl.init(); + + RepresentativeElectionRecipe createRepresentativeElectionRecipe(); + + Connectivity createConnectivityFromString(EDataType eDataType, String initialValue); + + String convertConnectivityToString(EDataType eDataType, Object instanceValue); +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesFactoryImpl.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesFactoryImpl.java new file mode 100644 index 00000000..4e2a695c --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesFactoryImpl.java @@ -0,0 +1,74 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.rete.recipe; + +import org.eclipse.emf.ecore.EClass; +import org.eclipse.emf.ecore.EDataType; +import org.eclipse.emf.ecore.EObject; +import org.eclipse.emf.ecore.EPackage; +import org.eclipse.emf.ecore.impl.EFactoryImpl; +import org.eclipse.emf.ecore.plugin.EcorePlugin; +import tools.refinery.store.query.literal.Connectivity; + +public class RefineryRecipesFactoryImpl extends EFactoryImpl implements RefineryRecipesFactory { + public static RefineryRecipesFactory init() { + try { + var factory = (RefineryRecipesFactory) EPackage.Registry.INSTANCE.getEFactory( + RefineryRecipesPackage.eNS_URI); + if (factory != null) { + return factory; + } + } + catch (Exception exception) { + EcorePlugin.INSTANCE.log(exception); + } + return new RefineryRecipesFactoryImpl(); + } + + @Override + public EObject create(EClass eClass) { + if (eClass.getClassifierID() == RefineryRecipesPackage.REPRESENTATIVE_ELECTION_RECIPE) { + return createRepresentativeElectionRecipe(); + } else { + throw new IllegalArgumentException("The class '%s' is not a valid classifier".formatted(eClass.getName())); + } + } + + @Override + public Object createFromString(EDataType eDataType, String stringValue) { + if (eDataType.getClassifierID() == RefineryRecipesPackage.CONNECTIVITY) { + return createConnectivityFromString(eDataType, stringValue); + } else { + throw new IllegalArgumentException("The datatype '%s' is not a valid classifier" + .formatted(eDataType.getName())); + } + } + + @Override + public String convertToString(EDataType eDataType, Object objectValue) { + if (eDataType.getClassifierID() == RefineryRecipesPackage.CONNECTIVITY) { + return convertConnectivityToString(eDataType, objectValue); + } else { + throw new IllegalArgumentException("The datatype '%s' is not a valid classifier" + .formatted(eDataType.getName())); + } + } + + @Override + public RepresentativeElectionRecipe createRepresentativeElectionRecipe() { + return new RepresentativeElectionRecipeImpl(); + } + + @Override + public Connectivity createConnectivityFromString(EDataType eDataType, String initialValue) { + return (Connectivity) super.createFromString(eDataType, initialValue); + } + + @Override + public String convertConnectivityToString(EDataType eDataType, Object instanceValue) { + return super.convertToString(eDataType, instanceValue); + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesPackage.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesPackage.java new file mode 100644 index 00000000..6c933c45 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesPackage.java @@ -0,0 +1,41 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.rete.recipe; + +import org.eclipse.emf.ecore.*; +import org.eclipse.viatra.query.runtime.rete.recipes.RecipesPackage; + +// Naming and index computation follows EMF conventions. +@SuppressWarnings({"squid:S100", "squid:S115", "PointlessArithmeticExpression"}) +public interface RefineryRecipesPackage extends EPackage { + String eNAME = "refineryReteRecipes"; + + String eNS_URI = "https://refinery.tools/emf/2021/RefineryReteRecipes"; + + String eNS_PREFIX = "refineryReteRecipes"; + + RefineryRecipesPackage eINSTANCE = RefineryRecipesPackageImpl.init(); + + int REPRESENTATIVE_ELECTION_RECIPE = 0; + + int REPRESENTATIVE_ELECTION_RECIPE__CONNECTIVITY = RecipesPackage.ALPHA_RECIPE_FEATURE_COUNT + 0; + + int REPRESENTATIVE_ELECTION_RECIPE_FEATURE_COUNT = RecipesPackage.ALPHA_RECIPE_FEATURE_COUNT + 1; + + int REPRESENTATIVE_ELECTION_RECIPE__GET_ARITY = RecipesPackage.ALPHA_RECIPE_OPERATION_COUNT + 0; + + int REPRESENTATIVE_ELECTION_RECIPE_OPERATION_COUNT = RecipesPackage.ALPHA_RECIPE_OPERATION_COUNT + 1; + + int CONNECTIVITY = 1; + + EClass getRepresentativeElectionRecipe(); + + EAttribute getRepresentativeElectionRecipe_Connectivity(); + + EOperation getRepresentativeElectionRecipe_GetArity(); + + EDataType getConnectivity(); +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesPackageImpl.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesPackageImpl.java new file mode 100644 index 00000000..d5073402 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RefineryRecipesPackageImpl.java @@ -0,0 +1,96 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.rete.recipe; + +import org.eclipse.emf.ecore.*; +import org.eclipse.emf.ecore.impl.EPackageImpl; +import org.eclipse.viatra.query.runtime.rete.recipes.RecipesPackage; +import tools.refinery.store.query.literal.Connectivity; + +public class RefineryRecipesPackageImpl extends EPackageImpl implements RefineryRecipesPackage { + private static boolean isInstanceInitialized; + private boolean isCreated; + private boolean isInitialized; + private EClass representativeElectionRecipe; + private EDataType connectivity; + + public static RefineryRecipesPackage init() { + if (isInstanceInitialized) { + return (RefineryRecipesPackage) Registry.INSTANCE.getEPackage(eNS_URI); + } + var thePackage = Registry.INSTANCE.get(eNS_URI) instanceof RefineryRecipesPackageImpl impl ? impl : + new RefineryRecipesPackageImpl(); + isInstanceInitialized = true; + thePackage.createPackageContents(); + thePackage.initializePackageContents(); + thePackage.freeze(); + Registry.INSTANCE.put(eNS_URI, thePackage); + return thePackage; + } + + private RefineryRecipesPackageImpl() { + super(eNS_URI, RefineryRecipesFactory.eINSTANCE); + } + + @Override + public EClass getRepresentativeElectionRecipe() { + return representativeElectionRecipe; + } + + @Override + public EAttribute getRepresentativeElectionRecipe_Connectivity() { + return (EAttribute) representativeElectionRecipe.getEStructuralFeatures().get(0); + } + + @Override + public EOperation getRepresentativeElectionRecipe_GetArity() { + return representativeElectionRecipe.getEOperations().get(0); + } + + @Override + public EDataType getConnectivity() { + return connectivity; + } + + public void createPackageContents() { + if (isCreated) { + return; + } + isCreated = true; + + representativeElectionRecipe = createEClass(REPRESENTATIVE_ELECTION_RECIPE); + createEAttribute(representativeElectionRecipe, REPRESENTATIVE_ELECTION_RECIPE__CONNECTIVITY); + createEOperation(representativeElectionRecipe, REPRESENTATIVE_ELECTION_RECIPE__GET_ARITY); + + connectivity = createEDataType(CONNECTIVITY); + } + + public void initializePackageContents() { + if (isInitialized) { + return; + } + isInitialized = true; + + setName(eNAME); + setNsPrefix(eNS_PREFIX); + setNsURI(eNS_URI); + + representativeElectionRecipe.getESuperTypes().add(RecipesPackage.Literals.ALPHA_RECIPE); + + initEClass(representativeElectionRecipe, RepresentativeElectionRecipe.class, + "RepresentativeElectionRecipe", !IS_ABSTRACT, !IS_INTERFACE, IS_GENERATED_INSTANCE_CLASS); + initEAttribute(getRepresentativeElectionRecipe_Connectivity(), getConnectivity(), "connectivity", null, 0, 1, + RepresentativeElectionRecipe.class, !IS_TRANSIENT, !IS_VOLATILE, IS_CHANGEABLE, !IS_UNSETTABLE, !IS_ID, + IS_UNIQUE, !IS_DERIVED, IS_ORDERED); + initEOperation(getRepresentativeElectionRecipe_GetArity(), EcorePackage.Literals.EINT, "getArity", 0, 1, + !IS_UNIQUE, IS_ORDERED); + + initEDataType(connectivity, Connectivity.class, "Connectivity", IS_SERIALIZABLE, + !IS_GENERATED_INSTANCE_CLASS); + + createResource(eNS_URI); + } +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RepresentativeElectionRecipe.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RepresentativeElectionRecipe.java new file mode 100644 index 00000000..def825c2 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RepresentativeElectionRecipe.java @@ -0,0 +1,17 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.rete.recipe; + +import org.eclipse.viatra.query.runtime.rete.recipes.AlphaRecipe; +import tools.refinery.store.query.literal.Connectivity; + +public interface RepresentativeElectionRecipe extends AlphaRecipe { + Connectivity getConnectivity(); + + void setConnectivity(Connectivity connectivity); + + int getArity(); +} diff --git a/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RepresentativeElectionRecipeImpl.java b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RepresentativeElectionRecipeImpl.java new file mode 100644 index 00000000..959836d2 --- /dev/null +++ b/subprojects/store-query-viatra/src/main/java/tools/refinery/store/query/viatra/internal/rete/recipe/RepresentativeElectionRecipeImpl.java @@ -0,0 +1,105 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra.internal.rete.recipe; + +import org.eclipse.emf.common.notify.Notification; +import org.eclipse.emf.common.util.EList; +import org.eclipse.emf.ecore.EClass; +import org.eclipse.emf.ecore.impl.ENotificationImpl; +import org.eclipse.viatra.query.runtime.rete.recipes.RecipesPackage; +import org.eclipse.viatra.query.runtime.rete.recipes.ReteNodeRecipe; +import org.eclipse.viatra.query.runtime.rete.recipes.impl.AlphaRecipeImpl; +import tools.refinery.store.query.literal.Connectivity; + +import java.lang.reflect.InvocationTargetException; + +public class RepresentativeElectionRecipeImpl extends AlphaRecipeImpl implements RepresentativeElectionRecipe { + private Connectivity connectivity; + + @Override + protected EClass eStaticClass() { + return RefineryRecipesPackage.eINSTANCE.getRepresentativeElectionRecipe(); + } + + @Override + public Connectivity getConnectivity() { + return connectivity; + } + + @Override + public void setConnectivity(Connectivity newStrong) { + var oldConnectivity = connectivity; + connectivity = newStrong; + if (eNotificationRequired()) { + eNotify(new ENotificationImpl(this, Notification.SET, + RefineryRecipesPackage.REPRESENTATIVE_ELECTION_RECIPE__CONNECTIVITY, oldConnectivity, + connectivity)); + } + } + + @Override + public int getArity() { + return 2; + } + + @Override + public Object eGet(int featureID, boolean resolve, boolean coreType) { + if (featureID == RefineryRecipesPackage.REPRESENTATIVE_ELECTION_RECIPE__CONNECTIVITY) { + return getConnectivity(); + } + return super.eGet(featureID, resolve, coreType); + } + + @Override + public void eSet(int featureID, Object newValue) { + if (featureID == RefineryRecipesPackage.REPRESENTATIVE_ELECTION_RECIPE__CONNECTIVITY) { + setConnectivity((Connectivity) newValue); + } else { + super.eSet(featureID, newValue); + } + } + + @Override + public void eUnset(int featureID) { + if (featureID == RefineryRecipesPackage.REPRESENTATIVE_ELECTION_RECIPE__CONNECTIVITY) { + setConnectivity(null); + } else { + super.eUnset(featureID); + } + } + + @Override + public boolean eIsSet(int featureID) { + if (featureID == RefineryRecipesPackage.REPRESENTATIVE_ELECTION_RECIPE__CONNECTIVITY) { + return connectivity != null; + } + return super.eIsSet(featureID); + } + + @Override + public int eDerivedOperationID(int baseOperationID, Class baseClass) { + if (baseClass == ReteNodeRecipe.class && baseOperationID == RecipesPackage.RETE_NODE_RECIPE___GET_ARITY) { + return RefineryRecipesPackage.REPRESENTATIVE_ELECTION_RECIPE__GET_ARITY; + } + return super.eDerivedOperationID(baseOperationID, baseClass); + } + + @Override + public Object eInvoke(int operationID, EList arguments) throws InvocationTargetException { + if (operationID == RefineryRecipesPackage.REPRESENTATIVE_ELECTION_RECIPE__GET_ARITY) { + return getArity(); + } + return super.eInvoke(operationID, arguments); + } + + @Override + public String toString() { + if (eIsProxy()) { + return super.toString(); + } + return "%s (connectivity: %s)".formatted(super.toString(), connectivity); + } +} diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/StronglyConnectedComponentsTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/StronglyConnectedComponentsTest.java new file mode 100644 index 00000000..05ea1bbb --- /dev/null +++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/StronglyConnectedComponentsTest.java @@ -0,0 +1,217 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra; + +import org.junit.jupiter.api.Test; +import tools.refinery.store.model.ModelStore; +import tools.refinery.store.query.ModelQueryAdapter; +import tools.refinery.store.query.dnf.Query; +import tools.refinery.store.query.literal.Connectivity; +import tools.refinery.store.query.literal.RepresentativeElectionLiteral; +import tools.refinery.store.query.view.AnySymbolView; +import tools.refinery.store.query.view.KeyOnlyView; +import tools.refinery.store.representation.Symbol; +import tools.refinery.store.tuple.Tuple; + +import java.util.List; +import java.util.Map; + +import static org.hamcrest.MatcherAssert.assertThat; +import static org.hamcrest.Matchers.is; +import static tools.refinery.store.query.viatra.tests.QueryAssertions.assertResults; + +class StronglyConnectedComponentsTest { + private static final Symbol friend = Symbol.of("friend", 2); + private static final AnySymbolView friendView = new KeyOnlyView<>(friend); + + @Test + void symbolViewTest() { + var query = Query.of("SymbolViewRepresentative", (builder, p1, p2) -> builder + .clause(v1 -> List.of( + new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p1, v1), + new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p2, v1) + ))); + + var store = ModelStore.builder() + .symbols(friend) + .with(ViatraModelQueryAdapter.builder() + .queries(query)) + .build(); + + var model = store.createEmptyModel(); + var friendInterpretation = model.getInterpretation(friend); + var queryEngine = model.getAdapter(ModelQueryAdapter.class); + var resultSet = queryEngine.getResultSet(query); + + friendInterpretation.put(Tuple.of(0, 1), true); + friendInterpretation.put(Tuple.of(1, 0), true); + friendInterpretation.put(Tuple.of(1, 2), true); + queryEngine.flushChanges(); + + assertResults(Map.of( + Tuple.of(0, 0), true, + Tuple.of(0, 1), true, + Tuple.of(1, 0), true, + Tuple.of(1, 1), true, + Tuple.of(2, 2), true + ), resultSet); + } + + @Test + void symbolViewInsertTest() { + var query = Query.of("SymbolViewRepresentative", (builder, p1, p2) -> builder + .clause(v1 -> List.of( + new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p1, v1), + new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p2, v1) + ))); + + var store = ModelStore.builder() + .symbols(friend) + .with(ViatraModelQueryAdapter.builder() + .queries(query)) + .build(); + + var model = store.createEmptyModel(); + var friendInterpretation = model.getInterpretation(friend); + var queryEngine = model.getAdapter(ModelQueryAdapter.class); + var resultSet = queryEngine.getResultSet(query); + + friendInterpretation.put(Tuple.of(0, 1), true); + friendInterpretation.put(Tuple.of(1, 0), true); + friendInterpretation.put(Tuple.of(1, 2), true); + queryEngine.flushChanges(); + + friendInterpretation.put(Tuple.of(2, 0), true); + friendInterpretation.put(Tuple.of(0, 3), true); + queryEngine.flushChanges(); + + assertResults(Map.of( + Tuple.of(0, 0), true, + Tuple.of(0, 1), true, + Tuple.of(0, 2), true, + Tuple.of(1, 1), true, + Tuple.of(1, 0), true, + Tuple.of(1, 2), true, + Tuple.of(2, 0), true, + Tuple.of(2, 1), true, + Tuple.of(2, 2), true, + Tuple.of(3, 3), true + ), resultSet); + } + + @Test + void symbolViewDeleteTest() { + var query = Query.of("SymbolViewRepresentative", (builder, p1, p2) -> builder + .clause(v1 -> List.of( + new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p1, v1), + new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p2, v1) + ))); + + var store = ModelStore.builder() + .symbols(friend) + .with(ViatraModelQueryAdapter.builder() + .queries(query)) + .build(); + + var model = store.createEmptyModel(); + var friendInterpretation = model.getInterpretation(friend); + var queryEngine = model.getAdapter(ModelQueryAdapter.class); + var resultSet = queryEngine.getResultSet(query); + + friendInterpretation.put(Tuple.of(0, 1), true); + friendInterpretation.put(Tuple.of(1, 0), true); + friendInterpretation.put(Tuple.of(1, 2), true); + queryEngine.flushChanges(); + + friendInterpretation.put(Tuple.of(1, 0), false); + friendInterpretation.put(Tuple.of(1, 2), false); + queryEngine.flushChanges(); + + assertResults(Map.of( + Tuple.of(0, 0), true, + Tuple.of(1, 1), true + ), resultSet); + } + + @Test + void diagonalSymbolViewTest() { + var person = Symbol.of("Person", 1); + var personView = new KeyOnlyView<>(person); + + var query = Query.of("SymbolViewRepresentative", (builder, p1) -> builder + .clause( + personView.call(p1), + new RepresentativeElectionLiteral(Connectivity.STRONG, friendView, p1, p1) + )); + + var store = ModelStore.builder() + .symbols(person, friend) + .with(ViatraModelQueryAdapter.builder() + .queries(query)) + .build(); + + var model = store.createEmptyModel(); + var personInterpretation = model.getInterpretation(person); + var friendInterpretation = model.getInterpretation(friend); + var queryEngine = model.getAdapter(ModelQueryAdapter.class); + var resultSet = queryEngine.getResultSet(query); + + personInterpretation.put(Tuple.of(0), true); + personInterpretation.put(Tuple.of(1), true); + personInterpretation.put(Tuple.of(2), true); + + friendInterpretation.put(Tuple.of(0, 1), true); + friendInterpretation.put(Tuple.of(1, 0), true); + friendInterpretation.put(Tuple.of(1, 2), true); + queryEngine.flushChanges(); + + assertThat(resultSet.size(), is(2)); + assertThat(resultSet.get(Tuple.of(2)), is(true)); + } + + @Test + void diagonalDnfTest() { + var person = Symbol.of("Person", 1); + var personView = new KeyOnlyView<>(person); + + var subQuery = Query.of("SubQuery", (builder, p1, p2) -> builder + .clause( + personView.call(p1), + personView.call(p2), + friendView.call(p1, p2) + )) + .getDnf(); + var query = Query.of("SymbolViewRepresentative", (builder, p1) -> builder + .clause( + personView.call(p1), + new RepresentativeElectionLiteral(Connectivity.STRONG, subQuery, p1, p1) + )); + + var store = ModelStore.builder() + .symbols(person, friend) + .with(ViatraModelQueryAdapter.builder() + .queries(query)) + .build(); + + var model = store.createEmptyModel(); + var personInterpretation = model.getInterpretation(person); + var friendInterpretation = model.getInterpretation(friend); + var queryEngine = model.getAdapter(ModelQueryAdapter.class); + var resultSet = queryEngine.getResultSet(query); + + personInterpretation.put(Tuple.of(0), true); + personInterpretation.put(Tuple.of(1), true); + personInterpretation.put(Tuple.of(2), true); + + friendInterpretation.put(Tuple.of(0, 1), true); + friendInterpretation.put(Tuple.of(1, 0), true); + friendInterpretation.put(Tuple.of(1, 2), true); + queryEngine.flushChanges(); + + assertThat(resultSet.size(), is(2)); + assertThat(resultSet.get(Tuple.of(2)), is(true)); + } +} diff --git a/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/WeaklyConnectedComponentsTest.java b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/WeaklyConnectedComponentsTest.java new file mode 100644 index 00000000..613d4284 --- /dev/null +++ b/subprojects/store-query-viatra/src/test/java/tools/refinery/store/query/viatra/WeaklyConnectedComponentsTest.java @@ -0,0 +1,188 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.viatra; + +import org.junit.jupiter.api.Test; +import tools.refinery.store.model.ModelStore; +import tools.refinery.store.query.ModelQueryAdapter; +import tools.refinery.store.query.dnf.Query; +import tools.refinery.store.query.literal.Connectivity; +import tools.refinery.store.query.literal.RepresentativeElectionLiteral; +import tools.refinery.store.query.view.AnySymbolView; +import tools.refinery.store.query.view.KeyOnlyView; +import tools.refinery.store.representation.Symbol; +import tools.refinery.store.tuple.Tuple; + +import java.util.List; +import java.util.Map; + +import static org.hamcrest.MatcherAssert.assertThat; +import static org.hamcrest.Matchers.is; +import static tools.refinery.store.query.viatra.tests.QueryAssertions.assertResults; + +class WeaklyConnectedComponentsTest { + private static final Symbol friend = Symbol.of("friend", 2); + private static final AnySymbolView friendView = new KeyOnlyView<>(friend); + + @Test + void symbolViewTest() { + var query = Query.of("SymbolViewRepresentative", (builder, p1, p2) -> builder + .clause(v1 -> List.of( + new RepresentativeElectionLiteral(Connectivity.WEAK, friendView, p1, v1), + new RepresentativeElectionLiteral(Connectivity.WEAK, friendView, p2, v1) + ))); + + var store = ModelStore.builder() + .symbols(friend) + .with(ViatraModelQueryAdapter.builder() + .queries(query)) + .build(); + + var model = store.createEmptyModel(); + var friendInterpretation = model.getInterpretation(friend); + var queryEngine = model.getAdapter(ModelQueryAdapter.class); + var resultSet = queryEngine.getResultSet(query); + + friendInterpretation.put(Tuple.of(0, 1), true); + friendInterpretation.put(Tuple.of(1, 0), true); + friendInterpretation.put(Tuple.of(2, 3), true); + queryEngine.flushChanges(); + + assertResults(Map.of( + Tuple.of(0, 0), true, + Tuple.of(0, 1), true, + Tuple.of(1, 0), true, + Tuple.of(1, 1), true, + Tuple.of(2, 2), true, + Tuple.of(2, 3), true, + Tuple.of(3, 2), true, + Tuple.of(3, 3), true + ), resultSet); + } + + @Test + void symbolViewUpdateTest() { + var query = Query.of("SymbolViewRepresentative", (builder, p1, p2) -> builder + .clause(v1 -> List.of( + new RepresentativeElectionLiteral(Connectivity.WEAK, friendView, p1, v1), + new RepresentativeElectionLiteral(Connectivity.WEAK, friendView, p2, v1) + ))); + + var store = ModelStore.builder() + .symbols(friend) + .with(ViatraModelQueryAdapter.builder() + .queries(query)) + .build(); + + var model = store.createEmptyModel(); + var friendInterpretation = model.getInterpretation(friend); + var queryEngine = model.getAdapter(ModelQueryAdapter.class); + var resultSet = queryEngine.getResultSet(query); + + friendInterpretation.put(Tuple.of(0, 1), true); + friendInterpretation.put(Tuple.of(1, 0), true); + friendInterpretation.put(Tuple.of(2, 3), true); + queryEngine.flushChanges(); + + friendInterpretation.put(Tuple.of(2, 3), false); + friendInterpretation.put(Tuple.of(1, 0), false); + friendInterpretation.put(Tuple.of(1, 2), true); + queryEngine.flushChanges(); + + assertResults(Map.of( + Tuple.of(0, 0), true, + Tuple.of(0, 1), true, + Tuple.of(0, 2), true, + Tuple.of(1, 0), true, + Tuple.of(1, 1), true, + Tuple.of(1, 2), true, + Tuple.of(2, 0), true, + Tuple.of(2, 1), true, + Tuple.of(2, 2), true + ), resultSet); + } + + @Test + void diagonalSymbolViewTest() { + var person = Symbol.of("Person", 1); + var personView = new KeyOnlyView<>(person); + + var query = Query.of("SymbolViewRepresentative", (builder, p1) -> builder + .clause( + personView.call(p1), + new RepresentativeElectionLiteral(Connectivity.WEAK, friendView, p1, p1) + )); + + var store = ModelStore.builder() + .symbols(person, friend) + .with(ViatraModelQueryAdapter.builder() + .queries(query)) + .build(); + + var model = store.createEmptyModel(); + var personInterpretation = model.getInterpretation(person); + var friendInterpretation = model.getInterpretation(friend); + var queryEngine = model.getAdapter(ModelQueryAdapter.class); + var resultSet = queryEngine.getResultSet(query); + + personInterpretation.put(Tuple.of(0), true); + personInterpretation.put(Tuple.of(1), true); + personInterpretation.put(Tuple.of(2), true); + personInterpretation.put(Tuple.of(3), true); + + friendInterpretation.put(Tuple.of(0, 1), true); + friendInterpretation.put(Tuple.of(1, 0), true); + friendInterpretation.put(Tuple.of(2, 3), true); + queryEngine.flushChanges(); + + assertThat(resultSet.size(), is(2)); + assertThat(resultSet.get(Tuple.of(2)), is(true)); + } + + @Test + void diagonalDnfTest() { + var person = Symbol.of("Person", 1); + var personView = new KeyOnlyView<>(person); + + var subQuery = Query.of("SubQuery", (builder, p1, p2) -> builder + .clause( + personView.call(p1), + personView.call(p2), + friendView.call(p1, p2) + )) + .getDnf(); + var query = Query.of("SymbolViewRepresentative", (builder, p1) -> builder + .clause( + personView.call(p1), + new RepresentativeElectionLiteral(Connectivity.WEAK, subQuery, p1, p1) + )); + + var store = ModelStore.builder() + .symbols(person, friend) + .with(ViatraModelQueryAdapter.builder() + .queries(query)) + .build(); + + var model = store.createEmptyModel(); + var personInterpretation = model.getInterpretation(person); + var friendInterpretation = model.getInterpretation(friend); + var queryEngine = model.getAdapter(ModelQueryAdapter.class); + var resultSet = queryEngine.getResultSet(query); + + personInterpretation.put(Tuple.of(0), true); + personInterpretation.put(Tuple.of(1), true); + personInterpretation.put(Tuple.of(2), true); + personInterpretation.put(Tuple.of(3), true); + + friendInterpretation.put(Tuple.of(0, 1), true); + friendInterpretation.put(Tuple.of(1, 0), true); + friendInterpretation.put(Tuple.of(2, 3), true); + queryEngine.flushChanges(); + + assertThat(resultSet.size(), is(2)); + assertThat(resultSet.get(Tuple.of(2)), is(true)); + } +} diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallLiteral.java index b1585c77..3a80cefd 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallLiteral.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/CallLiteral.java @@ -30,6 +30,10 @@ public final class CallLiteral extends AbstractCallLiteral implements CanNegate< if (parameters.get(0).isDataVariable() || parameters.get(1).isDataVariable()) { throw new IllegalArgumentException("Transitive closures can only be computed over nodes"); } + if (parameters.get(0).getDirection() != ParameterDirection.OUT || + parameters.get(1).getDirection() != ParameterDirection.OUT) { + throw new IllegalArgumentException("Transitive closures cannot take input parameters"); + } } this.polarity = polarity; } diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Connectivity.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Connectivity.java new file mode 100644 index 00000000..a058094d --- /dev/null +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/Connectivity.java @@ -0,0 +1,18 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.literal; + +import java.util.Locale; + +public enum Connectivity { + WEAK, + STRONG; + + @Override + public String toString() { + return name().toLowerCase(Locale.ROOT); + } +} diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/RepresentativeElectionLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/RepresentativeElectionLiteral.java new file mode 100644 index 00000000..876ae253 --- /dev/null +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/RepresentativeElectionLiteral.java @@ -0,0 +1,102 @@ +/* + * SPDX-FileCopyrightText: 2023 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.literal; + +import tools.refinery.store.query.Constraint; +import tools.refinery.store.query.substitution.Substitution; +import tools.refinery.store.query.term.NodeVariable; +import tools.refinery.store.query.term.ParameterDirection; +import tools.refinery.store.query.term.Variable; + +import java.util.List; +import java.util.Set; + +// {@link Object#equals(Object)} is implemented by {@link AbstractLiteral}. +@SuppressWarnings("squid:S2160") +public class RepresentativeElectionLiteral extends AbstractCallLiteral { + private final Connectivity connectivity; + + public RepresentativeElectionLiteral(Connectivity connectivity, Constraint target, NodeVariable specific, + NodeVariable representative) { + this(connectivity, target, List.of(specific, representative)); + } + + private RepresentativeElectionLiteral(Connectivity connectivity, Constraint target, List arguments) { + super(target, arguments); + this.connectivity = connectivity; + var parameters = target.getParameters(); + int arity = target.arity(); + if (arity != 2) { + throw new IllegalArgumentException("SCCs can only take binary relations"); + } + if (parameters.get(0).isDataVariable() || parameters.get(1).isDataVariable()) { + throw new IllegalArgumentException("SCCs can only be computed over nodes"); + } + if (parameters.get(0).getDirection() != ParameterDirection.OUT || + parameters.get(1).getDirection() != ParameterDirection.OUT) { + throw new IllegalArgumentException("SCCs cannot take input parameters"); + } + } + + public Connectivity getConnectivity() { + return connectivity; + } + + @Override + protected Literal doSubstitute(Substitution substitution, List substitutedArguments) { + return new RepresentativeElectionLiteral(connectivity, getTarget(), substitutedArguments); + } + + @Override + public Set getOutputVariables() { + return getArgumentsOfDirection(ParameterDirection.OUT); + } + + @Override + public Set getInputVariables(Set positiveVariablesInClause) { + return Set.of(); + } + + @Override + public Set getPrivateVariables(Set positiveVariablesInClause) { + return Set.of(); + } + + @Override + public Literal reduce() { + var reduction = getTarget().getReduction(); + return switch (reduction) { + case ALWAYS_FALSE -> BooleanLiteral.FALSE; + case ALWAYS_TRUE -> throw new IllegalArgumentException( + "Trying to elect representatives over an infinite set"); + case NOT_REDUCIBLE -> this; + }; + } + + @Override + protected AbstractCallLiteral internalWithTarget(Constraint newTarget) { + return new RepresentativeElectionLiteral(connectivity, newTarget, getArguments()); + } + + @Override + public String toString() { + var builder = new StringBuilder(); + builder.append("@Representative(\""); + builder.append(connectivity); + builder.append("\") "); + builder.append(getTarget().toReferenceString()); + builder.append("("); + var argumentIterator = getArguments().iterator(); + if (argumentIterator.hasNext()) { + builder.append(argumentIterator.next()); + while (argumentIterator.hasNext()) { + builder.append(", ").append(argumentIterator.next()); + } + } + builder.append(")"); + return builder.toString(); + } +} diff --git a/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/lifting/ClauseLifter.java b/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/lifting/ClauseLifter.java index 7bf092a3..89e948dc 100644 --- a/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/lifting/ClauseLifter.java +++ b/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/lifting/ClauseLifter.java @@ -74,6 +74,8 @@ class ClauseLifter { throw new IllegalArgumentException("Count literal %s cannot be lifted".formatted(literal)); } else if (literal instanceof AggregationLiteral) { throw new IllegalArgumentException("Aggregation literal %s cannot be lifted".formatted(literal)); + } else if (literal instanceof RepresentativeElectionLiteral) { + throw new IllegalArgumentException("SCC literal %s cannot be lifted".formatted(literal)); } else { throw new IllegalArgumentException("Unknown literal to lift: " + literal); } diff --git a/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/lifting/DnfLifter.java b/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/lifting/DnfLifter.java index 6ac3efc0..f878b674 100644 --- a/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/lifting/DnfLifter.java +++ b/subprojects/store-reasoning/src/main/java/tools/refinery/store/reasoning/lifting/DnfLifter.java @@ -23,7 +23,7 @@ public class DnfLifter { return query.withDnf(liftedDnf); } - public RelationalQuery lift(Modality modality, Concreteness concreteness, RelationalQuery query) { + public RelationalQuery lift(Modality modality, Concreteness concreteness, RelationalQuery query) { var liftedDnf = lift(modality, concreteness, query.getDnf()); return query.withDnf(liftedDnf); } -- cgit v1.2.3-70-g09d2