From 31465875054c847943e625d9e84bbbd52bc3695e Mon Sep 17 00:00:00 2001 From: Kristóf Marussy Date: Thu, 22 Feb 2024 02:02:21 +0100 Subject: feat(query): left join for data variables --- .../src/main/resources/model/recipes.ecore | 11 + .../src/main/resources/model/recipes.ecore.license | 2 +- .../src/main/resources/model/rete-recipes.genmodel | 9 +- .../resources/model/rete-recipes.genmodel.license | 2 +- .../interpreter/rete/aggregation/LeftJoinNode.java | 167 ++ .../plancompiler/ReteRecipeCompiler.java | 1815 ++++++++++---------- .../rete/network/ConnectionFactory.java | 10 +- .../interpreter/rete/network/NodeFactory.java | 38 +- .../psystem/basicdeferred/LeftJoinConstraint.java | 82 + .../matchers/psystem/rewriters/PBodyCopier.java | 13 +- .../ProblemSemanticHighlightingCalculator.java | 1 - .../interpreter/internal/pquery/Dnf2PQuery.java | 101 +- .../query/interpreter/FunctionalQueryTest.java | 1 - .../store/query/interpreter/LeftJoinTest.java | 129 ++ .../tools/refinery/store/query/Constraint.java | 12 +- .../store/query/dnf/ClausePostProcessor.java | 6 +- .../refinery/store/query/dnf/DnfPostProcessor.java | 4 +- .../refinery/store/query/dnf/FunctionalQuery.java | 18 +- .../store/query/literal/AggregationLiteral.java | 9 +- .../store/query/literal/LeftJoinLiteral.java | 140 ++ .../refinery/store/query/view/FunctionView.java | 16 +- 21 files changed, 1636 insertions(+), 950 deletions(-) create mode 100644 subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/aggregation/LeftJoinNode.java create mode 100644 subprojects/interpreter/src/main/java/tools/refinery/interpreter/matchers/psystem/basicdeferred/LeftJoinConstraint.java create mode 100644 subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/LeftJoinTest.java create mode 100644 subprojects/store-query/src/main/java/tools/refinery/store/query/literal/LeftJoinLiteral.java (limited to 'subprojects') diff --git a/subprojects/interpreter-rete-recipes/src/main/resources/model/recipes.ecore b/subprojects/interpreter-rete-recipes/src/main/resources/model/recipes.ecore index 6b8f10ea..23ee5a77 100644 --- a/subprojects/interpreter-rete-recipes/src/main/resources/model/recipes.ecore +++ b/subprojects/interpreter-rete-recipes/src/main/resources/model/recipes.ecore @@ -399,4 +399,15 @@ + + + +
+ + + + + + diff --git a/subprojects/interpreter-rete-recipes/src/main/resources/model/recipes.ecore.license b/subprojects/interpreter-rete-recipes/src/main/resources/model/recipes.ecore.license index 03d1d42b..22023c2c 100644 --- a/subprojects/interpreter-rete-recipes/src/main/resources/model/recipes.ecore.license +++ b/subprojects/interpreter-rete-recipes/src/main/resources/model/recipes.ecore.license @@ -1,4 +1,4 @@ Copyright (c) 2004-2014 Gabor Bergmann and Daniel Varro -Copyright (c) 2023 The Refinery Authors +Copyright (c) 2023-2024 The Refinery Authors SPDX-License-Identifier: EPL-2.0 diff --git a/subprojects/interpreter-rete-recipes/src/main/resources/model/rete-recipes.genmodel b/subprojects/interpreter-rete-recipes/src/main/resources/model/rete-recipes.genmodel index f7dc7a4e..f156b1a2 100644 --- a/subprojects/interpreter-rete-recipes/src/main/resources/model/rete-recipes.genmodel +++ b/subprojects/interpreter-rete-recipes/src/main/resources/model/rete-recipes.genmodel @@ -1,6 +1,6 @@ + + + + + + diff --git a/subprojects/interpreter-rete-recipes/src/main/resources/model/rete-recipes.genmodel.license b/subprojects/interpreter-rete-recipes/src/main/resources/model/rete-recipes.genmodel.license index 03d1d42b..22023c2c 100644 --- a/subprojects/interpreter-rete-recipes/src/main/resources/model/rete-recipes.genmodel.license +++ b/subprojects/interpreter-rete-recipes/src/main/resources/model/rete-recipes.genmodel.license @@ -1,4 +1,4 @@ Copyright (c) 2004-2014 Gabor Bergmann and Daniel Varro -Copyright (c) 2023 The Refinery Authors +Copyright (c) 2023-2024 The Refinery Authors SPDX-License-Identifier: EPL-2.0 diff --git a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/aggregation/LeftJoinNode.java b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/aggregation/LeftJoinNode.java new file mode 100644 index 00000000..9871e3bc --- /dev/null +++ b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/aggregation/LeftJoinNode.java @@ -0,0 +1,167 @@ +/******************************************************************************* + * Copyright (c) 2004-2009 Gabor Bergmann and Daniel Varro + * Copyright (c) 2024 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.interpreter.rete.aggregation; + +import tools.refinery.interpreter.matchers.tuple.ITuple; +import tools.refinery.interpreter.matchers.tuple.Tuple; +import tools.refinery.interpreter.matchers.tuple.TupleMask; +import tools.refinery.interpreter.matchers.tuple.Tuples; +import tools.refinery.interpreter.matchers.util.Direction; +import tools.refinery.interpreter.matchers.util.timeline.Timeline; +import tools.refinery.interpreter.rete.index.DefaultIndexerListener; +import tools.refinery.interpreter.rete.index.Indexer; +import tools.refinery.interpreter.rete.index.ProjectionIndexer; +import tools.refinery.interpreter.rete.index.StandardIndexer; +import tools.refinery.interpreter.rete.network.Node; +import tools.refinery.interpreter.rete.network.ReteContainer; +import tools.refinery.interpreter.rete.network.StandardNode; +import tools.refinery.interpreter.rete.network.communication.Timestamp; + +import java.util.Collection; +import java.util.List; +import java.util.Map; +import java.util.Set; + +public class LeftJoinNode extends StandardNode { + private final Object defaultValue; + private ProjectionIndexer projectionIndexer; + private TupleMask projectionMask; + private boolean leftInheritanceOutputMask; + private OuterIndexer outerIndexer = null; + + public LeftJoinNode(ReteContainer reteContainer, Object defaultValue) { + super(reteContainer); + this.defaultValue = defaultValue; + } + + @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 initializeWith(ProjectionIndexer projectionIndexer) { + this.projectionIndexer = projectionIndexer; + projectionMask = projectionIndexer.getMask(); + leftInheritanceOutputMask = isLeftInheritanceOutputMask(projectionMask); + projectionIndexer.attachListener(new DefaultIndexerListener(this) { + @Override + public void notifyIndexerUpdate(Direction direction, Tuple updateElement, Tuple signature, boolean change, + Timestamp timestamp) { + update(direction, updateElement, signature, change, timestamp); + } + }); + } + + private static boolean isLeftInheritanceOutputMask(TupleMask mask) { + int size = mask.getSize(); + int sourceWidth = mask.getSourceWidth(); + if (size != sourceWidth - 1) { + throw new IllegalArgumentException("projectionMask should omit a single index, got " + mask); + } + int[] repetitions = new int[sourceWidth]; + for (int i = 0; i < size; i++) { + int index = mask.indices[i]; + int repetition = repetitions[index] + 1; + if (repetition >= 2) { + throw new IllegalArgumentException("Repeated index %d in projectionMask %s".formatted(index, mask)); + } + repetitions[index] = repetition; + } + for (int i = 0; i < size; i++) { + int index = mask.indices[i]; + if (index != i) { + return false; + } + } + return true; + } + + protected void update(Direction direction, Tuple updateElement, Tuple signature, boolean change, + Timestamp timestamp) { + propagateUpdate(direction, updateElement, timestamp); + if (outerIndexer != null) { + outerIndexer.update(direction, updateElement, signature, change, timestamp); + } + } + + protected Tuple getDefaultTuple(ITuple key) { + if (leftInheritanceOutputMask) { + return Tuples.staticArityFlatTupleOf(key, defaultValue); + } + var objects = new Object[projectionMask.sourceWidth]; + int targetLength = projectionMask.indices.length; + for (int i = 0; i < targetLength; i++) { + int j = projectionMask.indices[i]; + objects[j] = key.get(j); + } + return Tuples.flatTupleOf(objects); + } + + @Override + public void pullInto(Collection collector, boolean flush) { + projectionIndexer.getParent().pullInto(collector, flush); + } + + @Override + public void pullIntoWithTimeline(Map> collector, boolean flush) { + projectionIndexer.getParent().pullIntoWithTimeline(collector, flush); + } + + @Override + public Set getPulledContents(boolean flush) { + return projectionIndexer.getParent().getPulledContents(flush); + } + + public Indexer getOuterIndexer() { + if (outerIndexer == null) { + outerIndexer = new OuterIndexer(); + getCommunicationTracker().registerDependency(this, outerIndexer); + } + return outerIndexer; + } + + /** + * A special non-iterable index that retrieves the aggregated, packed result (signature+aggregate) for the original + * signature. + * + * @author Gabor Bergmann + */ + class OuterIndexer extends StandardIndexer { + public OuterIndexer() { + super(LeftJoinNode.this.reteContainer, LeftJoinNode.this.projectionMask); + this.parent = LeftJoinNode.this; + } + + @Override + public Collection get(Tuple signature) { + var collection = projectionIndexer.get(signature); + if (collection == null || collection.isEmpty()) { + return List.of(getDefaultTuple(signature)); + } + return collection; + } + + public void update(Direction direction, Tuple updateElement, Tuple signature, boolean change, + Timestamp timestamp) { + propagate(direction, updateElement, signature, false, timestamp); + if (change) { + var defaultTuple = getDefaultTuple(signature); + propagate(direction.opposite(), defaultTuple, signature, false, timestamp); + } + } + + @Override + public Node getActiveNode() { + return projectionIndexer.getActiveNode(); + } + } +} diff --git a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/construction/plancompiler/ReteRecipeCompiler.java b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/construction/plancompiler/ReteRecipeCompiler.java index f84eae0a..52a4de41 100644 --- a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/construction/plancompiler/ReteRecipeCompiler.java +++ b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/construction/plancompiler/ReteRecipeCompiler.java @@ -10,6 +10,7 @@ package tools.refinery.interpreter.rete.construction.plancompiler; import org.apache.log4j.Logger; +import org.eclipse.emf.ecore.util.EcoreUtil; import tools.refinery.interpreter.matchers.InterpreterRuntimeException; import tools.refinery.interpreter.matchers.backend.CommonQueryHintOptions; import tools.refinery.interpreter.matchers.backend.IQueryBackendHintProvider; @@ -53,782 +54,843 @@ import java.util.function.Function; * {@link CompiledSubPlan}. * * @author Bergmann Gabor - * */ public class ReteRecipeCompiler { - private final IQueryPlannerStrategy plannerStrategy; - private final IQueryMetaContext metaContext; - private final IQueryBackendHintProvider hintProvider; - private final PDisjunctionRewriter normalizer; - private final QueryAnalyzer queryAnalyzer; - private final Logger logger; - - /** - * @since 2.2 - */ - protected final boolean deleteAndRederiveEvaluation; - /** - * @since 2.4 - */ - protected final TimelyConfiguration timelyEvaluation; - - /** - * @since 1.5 - */ - public ReteRecipeCompiler(IQueryPlannerStrategy plannerStrategy, Logger logger, IQueryMetaContext metaContext, - IQueryCacheContext queryCacheContext, IQueryBackendHintProvider hintProvider, QueryAnalyzer queryAnalyzer) { - this(plannerStrategy, logger, metaContext, queryCacheContext, hintProvider, queryAnalyzer, false, null); - } - - /** - * @since 2.4 - */ - public ReteRecipeCompiler(IQueryPlannerStrategy plannerStrategy, Logger logger, IQueryMetaContext metaContext, - IQueryCacheContext queryCacheContext, IQueryBackendHintProvider hintProvider, QueryAnalyzer queryAnalyzer, - boolean deleteAndRederiveEvaluation, TimelyConfiguration timelyEvaluation) { - super(); - this.deleteAndRederiveEvaluation = deleteAndRederiveEvaluation; - this.timelyEvaluation = timelyEvaluation; - this.plannerStrategy = plannerStrategy; - this.logger = logger; - this.metaContext = metaContext; - this.queryAnalyzer = queryAnalyzer; - this.normalizer = new PDisjunctionRewriterCacher(new SurrogateQueryRewriter(), - new PBodyNormalizer(metaContext) { - - @Override - protected boolean shouldExpandWeakenedAlternatives(PQuery query) { - QueryEvaluationHint hint = ReteRecipeCompiler.this.hintProvider.getQueryEvaluationHint(query); - Boolean expandWeakenedAlternativeConstraints = ReteHintOptions.expandWeakenedAlternativeConstraints - .getValueOrDefault(hint); - return expandWeakenedAlternativeConstraints; - } - - }); - this.hintProvider = hintProvider; - } - - static final RecipesFactory FACTORY = RecipesFactory.eINSTANCE; - - // INTERNALLY CACHED - private Map plannerCache = new HashMap(); - private Set planningInProgress = new HashSet(); - - private Map queryCompilerCache = new HashMap(); - private Set compilationInProgress = new HashSet(); - private IMultiLookup recursionCutoffPoints = CollectionsFactory.createMultiLookup(Object.class, MemoryType.SETS, Object.class); - private Map subPlanCompilerCache = new HashMap(); - private Map compilerBackTrace = new HashMap(); - - /** - * Clears internal state - */ - public void reset() { - plannerCache.clear(); - planningInProgress.clear(); - queryCompilerCache.clear(); - subPlanCompilerCache.clear(); - compilerBackTrace.clear(); - } - - /** - * Returns a {@link CompiledQuery} compiled from a query - * @throws InterpreterRuntimeException - */ - public CompiledQuery getCompiledForm(PQuery query) { - CompiledQuery compiled = queryCompilerCache.get(query); - if (compiled == null) { - - IRewriterTraceCollector traceCollector = CommonQueryHintOptions.normalizationTraceCollector - .getValueOrDefault(hintProvider.getQueryEvaluationHint(query)); - if (traceCollector != null) { - traceCollector.addTrace(query, query); - } - - boolean reentrant = !compilationInProgress.add(query); - if (reentrant) { // oops, recursion into body in progress - RecursionCutoffPoint cutoffPoint = new RecursionCutoffPoint(query, getHints(query), metaContext, - deleteAndRederiveEvaluation, timelyEvaluation); - recursionCutoffPoints.addPair(query, cutoffPoint); - return cutoffPoint.getCompiledQuery(); - } else { // not reentrant, therefore no recursion, do the compilation - try { - compiled = compileProduction(query); - queryCompilerCache.put(query, compiled); - // backTrace.put(compiled.getRecipe(), plan); - - // if this was a recursive query, mend all points where recursion was cut off - for (RecursionCutoffPoint cutoffPoint : recursionCutoffPoints.lookupOrEmpty(query)) { - cutoffPoint.mend(compiled); - } - } finally { - compilationInProgress.remove(query); - } - } - } - return compiled; - } - - /** - * Returns a {@link CompiledSubPlan} compiled from a query plan - * @throws InterpreterRuntimeException - */ - public CompiledSubPlan getCompiledForm(SubPlan plan) { - CompiledSubPlan compiled = subPlanCompilerCache.get(plan); - if (compiled == null) { - compiled = doCompileDispatch(plan); - subPlanCompilerCache.put(plan, compiled); - compilerBackTrace.put(compiled.getRecipe(), plan); - } - return compiled; - } - - /** - * @throws InterpreterRuntimeException - */ - public SubPlan getPlan(PBody pBody) { - // if the query is not marked as being compiled, initiate compilation - // (this is useful in case of recursion if getPlan() is the entry point) - PQuery pQuery = pBody.getPattern(); - if (!compilationInProgress.contains(pQuery)) - getCompiledForm(pQuery); - - // Is the plan already cached? - SubPlan plan = plannerCache.get(pBody); - if (plan == null) { - boolean reentrant = !planningInProgress.add(pBody); - if (reentrant) { // oops, recursion into body in progress - throw new IllegalArgumentException( - "Planning-level recursion unsupported: " + pBody.getPattern().getFullyQualifiedName()); - } else { // not reentrant, therefore no recursion, do the planning - try { - plan = plannerStrategy.plan(pBody, logger, metaContext); - plannerCache.put(pBody, plan); - } finally { - planningInProgress.remove(pBody); - } - } - } - return plan; - } - - private CompiledQuery compileProduction(PQuery query) { - Collection bodyPlans = new ArrayList(); - normalizer.setTraceCollector(CommonQueryHintOptions.normalizationTraceCollector - .getValueOrDefault(hintProvider.getQueryEvaluationHint(query))); - for (PBody pBody : normalizer.rewrite(query).getBodies()) { - SubPlan bodyPlan = getPlan(pBody); - bodyPlans.add(bodyPlan); - } - return doCompileProduction(query, bodyPlans); - } - - private CompiledQuery doCompileProduction(PQuery query, Collection bodies) { - // TODO skip production node if there is just one body and no projection needed? - Map bodyFinalTraces = new HashMap(); - Collection bodyFinalRecipes = new HashSet(); - - for (SubPlan bodyFinalPlan : bodies) { - // skip over any projections at the end - bodyFinalPlan = BuildHelper.eliminateTrailingProjections(bodyFinalPlan); - - // TODO checkAndTrimEqualVariables may introduce superfluous trim, - // but whatever (no uniqueness enforcer needed) - - // compile body - final CompiledSubPlan compiledBody = getCompiledForm(bodyFinalPlan); - - // project to parameter list - RecipeTraceInfo finalTrace = projectBodyFinalToParameters(compiledBody, false); - - bodyFinalTraces.put(bodyFinalPlan.getBody(), finalTrace); - bodyFinalRecipes.add(finalTrace.getRecipe()); - } - - CompiledQuery compiled = CompilerHelper.makeQueryTrace(query, bodyFinalTraces, bodyFinalRecipes, - getHints(query), metaContext, deleteAndRederiveEvaluation, timelyEvaluation); - - return compiled; - } - - private CompiledSubPlan doCompileDispatch(SubPlan plan) { - final POperation operation = plan.getOperation(); - if (operation instanceof PEnumerate) { - return doCompileEnumerate(((PEnumerate) operation).getEnumerablePConstraint(), plan); - } else if (operation instanceof PApply) { - final PConstraint pConstraint = ((PApply) operation).getPConstraint(); - if (pConstraint instanceof EnumerablePConstraint) { - CompiledSubPlan primaryParent = getCompiledForm(plan.getParentPlans().get(0)); - PlanningTrace secondaryParent = doEnumerateDispatch(plan, (EnumerablePConstraint) pConstraint); - return compileToNaturalJoin(plan, primaryParent, secondaryParent); - } else if (pConstraint instanceof DeferredPConstraint) { - return doDeferredDispatch((DeferredPConstraint) pConstraint, plan); - } else { - throw new IllegalArgumentException("Unsupported PConstraint in query plan: " + plan.toShortString()); - } - } else if (operation instanceof PJoin) { - return doCompileJoin((PJoin) operation, plan); - } else if (operation instanceof PProject) { - return doCompileProject((PProject) operation, plan); - } else if (operation instanceof PStart) { - return doCompileStart((PStart) operation, plan); - } else { - throw new IllegalArgumentException("Unsupported POperation in query plan: " + plan.toShortString()); - } - } - - private CompiledSubPlan doDeferredDispatch(DeferredPConstraint constraint, SubPlan plan) { - final SubPlan parentPlan = plan.getParentPlans().get(0); - final CompiledSubPlan parentCompiled = getCompiledForm(parentPlan); - if (constraint instanceof Equality) { - return compileDeferred((Equality) constraint, plan, parentPlan, parentCompiled); - } else if (constraint instanceof ExportedParameter) { - return compileDeferred((ExportedParameter) constraint, plan, parentPlan, parentCompiled); - } else if (constraint instanceof Inequality) { - return compileDeferred((Inequality) constraint, plan, parentPlan, parentCompiled); - } else if (constraint instanceof NegativePatternCall) { - return compileDeferred((NegativePatternCall) constraint, plan, parentPlan, parentCompiled); - } else if (constraint instanceof PatternMatchCounter) { - return compileDeferred((PatternMatchCounter) constraint, plan, parentPlan, parentCompiled); - } else if (constraint instanceof AggregatorConstraint) { - return compileDeferred((AggregatorConstraint) constraint, plan, parentPlan, parentCompiled); - } else if (constraint instanceof ExpressionEvaluation) { - return compileDeferred((ExpressionEvaluation) constraint, plan, parentPlan, parentCompiled); - } else if (constraint instanceof TypeFilterConstraint) { - return compileDeferred((TypeFilterConstraint) constraint, plan, parentPlan, parentCompiled); - } - throw new UnsupportedOperationException("Unknown deferred constraint " + constraint); - } - - private CompiledSubPlan compileDeferred(Equality constraint, SubPlan plan, SubPlan parentPlan, - CompiledSubPlan parentCompiled) { - if (constraint.isMoot()) - return parentCompiled.cloneFor(plan); - - Integer index1 = parentCompiled.getPosMapping().get(constraint.getWho()); - Integer index2 = parentCompiled.getPosMapping().get(constraint.getWithWhom()); - - if (index1 != null && index2 != null && index1.intValue() != index2.intValue()) { - Integer indexLower = Math.min(index1, index2); - Integer indexHigher = Math.max(index1, index2); - - EqualityFilterRecipe equalityFilterRecipe = FACTORY.createEqualityFilterRecipe(); - equalityFilterRecipe.setParent(parentCompiled.getRecipe()); - equalityFilterRecipe.getIndices().add(indexLower); - equalityFilterRecipe.getIndices().add(indexHigher); - - return new CompiledSubPlan(plan, parentCompiled.getVariablesTuple(), equalityFilterRecipe, parentCompiled); - } else { - throw new IllegalArgumentException(String.format("Unable to interpret %s after compiled parent %s", - plan.toShortString(), parentCompiled.toString())); - } - } - - /** - * Precondition: constantTrace must map to a ConstantRecipe, and all of its variables must be contained in - * toFilterTrace. - */ - private CompiledSubPlan compileConstantFiltering(SubPlan plan, PlanningTrace toFilterTrace, - ConstantRecipe constantRecipe, List filteredVariables) { - PlanningTrace resultTrace = toFilterTrace; - - int constantVariablesSize = filteredVariables.size(); - for (int i = 0; i < constantVariablesSize; ++i) { - Object constantValue = constantRecipe.getConstantValues().get(i); - PVariable filteredVariable = filteredVariables.get(i); - int filteredColumn = resultTrace.getVariablesTuple().indexOf(filteredVariable); - - DiscriminatorDispatcherRecipe dispatcherRecipe = FACTORY.createDiscriminatorDispatcherRecipe(); - dispatcherRecipe.setDiscriminationColumnIndex(filteredColumn); - dispatcherRecipe.setParent(resultTrace.getRecipe()); - - PlanningTrace dispatcherTrace = new PlanningTrace(plan, resultTrace.getVariablesTuple(), dispatcherRecipe, - resultTrace); - - DiscriminatorBucketRecipe bucketRecipe = FACTORY.createDiscriminatorBucketRecipe(); - bucketRecipe.setBucketKey(constantValue); - bucketRecipe.setParent(dispatcherRecipe); - - PlanningTrace bucketTrace = new PlanningTrace(plan, dispatcherTrace.getVariablesTuple(), bucketRecipe, - dispatcherTrace); - - resultTrace = bucketTrace; - } - - return resultTrace.cloneFor(plan); - } - - private CompiledSubPlan compileDeferred(ExportedParameter constraint, SubPlan plan, SubPlan parentPlan, - CompiledSubPlan parentCompiled) { - return parentCompiled.cloneFor(plan); - } - - private CompiledSubPlan compileDeferred(Inequality constraint, SubPlan plan, SubPlan parentPlan, - CompiledSubPlan parentCompiled) { - if (constraint.isEliminable()) - return parentCompiled.cloneFor(plan); - - Integer index1 = parentCompiled.getPosMapping().get(constraint.getWho()); - Integer index2 = parentCompiled.getPosMapping().get(constraint.getWithWhom()); - - if (index1 != null && index2 != null && index1.intValue() != index2.intValue()) { - Integer indexLower = Math.min(index1, index2); - Integer indexHigher = Math.max(index1, index2); - - InequalityFilterRecipe inequalityFilterRecipe = FACTORY.createInequalityFilterRecipe(); - inequalityFilterRecipe.setParent(parentCompiled.getRecipe()); - inequalityFilterRecipe.setSubject(indexLower); - inequalityFilterRecipe.getInequals().add(indexHigher); - - return new CompiledSubPlan(plan, parentCompiled.getVariablesTuple(), inequalityFilterRecipe, - parentCompiled); - } else { - throw new IllegalArgumentException(String.format("Unable to interpret %s after compiled parent %s", - plan.toShortString(), parentCompiled.toString())); - } - } - - private CompiledSubPlan compileDeferred(TypeFilterConstraint constraint, SubPlan plan, SubPlan parentPlan, - CompiledSubPlan parentCompiled) { - final IInputKey inputKey = constraint.getInputKey(); - if (!metaContext.isStateless(inputKey)) - throw new UnsupportedOperationException( - "Non-enumerable input keys are currently supported in Rete only if they are stateless, unlike " - + inputKey); - - final Tuple constraintVariables = constraint.getVariablesTuple(); - final List parentVariables = parentCompiled.getVariablesTuple(); - - Mask mask; // select elements of the tuple to check against extensional relation - if (Tuples.flatTupleOf(parentVariables.toArray()).equals(constraintVariables)) { - mask = null; // lucky case, parent signature equals that of input key - } else { - List variables = new ArrayList(); - for (Object variable : constraintVariables.getElements()) { - variables.add((PVariable) variable); - } - mask = CompilerHelper.makeProjectionMask(parentCompiled, variables); - } - InputFilterRecipe inputFilterRecipe = RecipesHelper.inputFilterRecipe(parentCompiled.getRecipe(), inputKey, - inputKey.getStringID(), mask); - return new CompiledSubPlan(plan, parentVariables, inputFilterRecipe, parentCompiled); - } - - private CompiledSubPlan compileDeferred(NegativePatternCall constraint, SubPlan plan, SubPlan parentPlan, - CompiledSubPlan parentCompiled) { - final PlanningTrace callTrace = referQuery(constraint.getReferredQuery(), plan, - constraint.getActualParametersTuple()); - - CompilerHelper.JoinHelper joinHelper = new CompilerHelper.JoinHelper(plan, parentCompiled, callTrace); - final RecipeTraceInfo primaryIndexer = joinHelper.getPrimaryIndexer(); - final RecipeTraceInfo secondaryIndexer = joinHelper.getSecondaryIndexer(); - - AntiJoinRecipe antiJoinRecipe = FACTORY.createAntiJoinRecipe(); - antiJoinRecipe.setLeftParent((ProjectionIndexerRecipe) primaryIndexer.getRecipe()); - antiJoinRecipe.setRightParent((IndexerRecipe) secondaryIndexer.getRecipe()); - - return new CompiledSubPlan(plan, parentCompiled.getVariablesTuple(), antiJoinRecipe, primaryIndexer, - secondaryIndexer); - } - - private CompiledSubPlan compileDeferred(PatternMatchCounter constraint, SubPlan plan, SubPlan parentPlan, - CompiledSubPlan parentCompiled) { - final PlanningTrace callTrace = referQuery(constraint.getReferredQuery(), plan, - constraint.getActualParametersTuple()); - - // hack: use some mask computations (+ the indexers) from a fake natural join against the called query - CompilerHelper.JoinHelper fakeJoinHelper = new CompilerHelper.JoinHelper(plan, parentCompiled, callTrace); - final RecipeTraceInfo primaryIndexer = fakeJoinHelper.getPrimaryIndexer(); - final RecipeTraceInfo callProjectionIndexer = fakeJoinHelper.getSecondaryIndexer(); - - final List sideVariablesTuple = new ArrayList( - fakeJoinHelper.getSecondaryMask().transform(callTrace.getVariablesTuple())); - /* if (!booleanCheck) */ sideVariablesTuple.add(constraint.getResultVariable()); - - CountAggregatorRecipe aggregatorRecipe = FACTORY.createCountAggregatorRecipe(); - aggregatorRecipe.setParent((ProjectionIndexerRecipe) callProjectionIndexer.getRecipe()); - PlanningTrace aggregatorTrace = new PlanningTrace(plan, sideVariablesTuple, aggregatorRecipe, - callProjectionIndexer); - - IndexerRecipe aggregatorIndexerRecipe = FACTORY.createAggregatorIndexerRecipe(); - aggregatorIndexerRecipe.setParent(aggregatorRecipe); - // aggregatorIndexerRecipe.setMask(RecipesHelper.mask( - // sideVariablesTuple.size(), - // //use same indices as in the projection indexer - // // EVEN if result variable already visible in left parent - // fakeJoinHelper.getSecondaryMask().indices - // )); - - int aggregatorWidth = sideVariablesTuple.size(); - int aggregateResultIndex = aggregatorWidth - 1; - - aggregatorIndexerRecipe.setMask(CompilerHelper.toRecipeMask(TupleMask.omit( - // aggregate according all but the last index - aggregateResultIndex, aggregatorWidth))); - PlanningTrace aggregatorIndexerTrace = new PlanningTrace(plan, sideVariablesTuple, aggregatorIndexerRecipe, - aggregatorTrace); - - JoinRecipe naturalJoinRecipe = FACTORY.createJoinRecipe(); - naturalJoinRecipe.setLeftParent((ProjectionIndexerRecipe) primaryIndexer.getRecipe()); - naturalJoinRecipe.setRightParent(aggregatorIndexerRecipe); - naturalJoinRecipe.setRightParentComplementaryMask(RecipesHelper.mask(aggregatorWidth, - // extend with last element only - the computation value - aggregateResultIndex)); - - // what if the new variable already has a value? - // even if already known, we add the new result variable, so that it can be filtered at the end - // boolean alreadyKnown = parentPlan.getVisibleVariables().contains(constraint.getResultVariable()); - - final List aggregatedVariablesTuple = new ArrayList(parentCompiled.getVariablesTuple()); - aggregatedVariablesTuple.add(constraint.getResultVariable()); - - PlanningTrace joinTrace = new PlanningTrace(plan, aggregatedVariablesTuple, naturalJoinRecipe, primaryIndexer, - aggregatorIndexerTrace); - - return CompilerHelper.checkAndTrimEqualVariables(plan, joinTrace).cloneFor(plan); - // if (!alreadyKnown) { - // return joinTrace.cloneFor(plan); - // } else { - // //final Integer equalsWithIndex = parentCompiled.getPosMapping().get(parentCompiled.getVariablesTuple()); - // } - } - - private CompiledSubPlan compileDeferred(AggregatorConstraint constraint, SubPlan plan, SubPlan parentPlan, - CompiledSubPlan parentCompiled) { - final PlanningTrace callTrace = referQuery(constraint.getReferredQuery(), plan, - constraint.getActualParametersTuple()); - - // hack: use some mask computations (+ the indexers) from a fake natural join against the called query - CompilerHelper.JoinHelper fakeJoinHelper = new CompilerHelper.JoinHelper(plan, parentCompiled, callTrace); - final RecipeTraceInfo primaryIndexer = fakeJoinHelper.getPrimaryIndexer(); - TupleMask callGroupMask = fakeJoinHelper.getSecondaryMask(); - - final List sideVariablesTuple = new ArrayList( - callGroupMask.transform(callTrace.getVariablesTuple())); - /* if (!booleanCheck) */ sideVariablesTuple.add(constraint.getResultVariable()); - - IMultisetAggregationOperator operator = constraint.getAggregator().getOperator(); - - SingleColumnAggregatorRecipe columnAggregatorRecipe = FACTORY.createSingleColumnAggregatorRecipe(); - columnAggregatorRecipe.setParent(callTrace.getRecipe()); - columnAggregatorRecipe.setMultisetAggregationOperator(operator); - - int columnIndex = constraint.getAggregatedColumn(); - IPosetComparator posetComparator = null; - Mask groupMask = CompilerHelper.toRecipeMask(callGroupMask); - - // temporary solution to support the deprecated option for now - final boolean deleteAndRederiveEvaluationDep = this.deleteAndRederiveEvaluation || ReteHintOptions.deleteRederiveEvaluation.getValueOrDefault(getHints(plan)); - - columnAggregatorRecipe.setDeleteRederiveEvaluation(deleteAndRederiveEvaluationDep); - if (deleteAndRederiveEvaluationDep || (this.timelyEvaluation != null)) { - List parameters = constraint.getReferredQuery().getParameters(); - IInputKey key = parameters.get(columnIndex).getDeclaredUnaryType(); - if (key != null && metaContext.isPosetKey(key)) { - posetComparator = metaContext.getPosetComparator(Collections.singleton(key)); - } - } - - if (posetComparator == null) { - columnAggregatorRecipe.setGroupByMask(groupMask); - columnAggregatorRecipe.setAggregableIndex(columnIndex); - } else { - MonotonicityInfo monotonicityInfo = FACTORY.createMonotonicityInfo(); - monotonicityInfo.setCoreMask(groupMask); - monotonicityInfo.setPosetMask(CompilerHelper.toRecipeMask( - TupleMask.selectSingle(columnIndex, constraint.getActualParametersTuple().getSize()))); - monotonicityInfo.setPosetComparator(posetComparator); - columnAggregatorRecipe.setOptionalMonotonicityInfo(monotonicityInfo); - } - - ReteNodeRecipe aggregatorRecipe = columnAggregatorRecipe; - PlanningTrace aggregatorTrace = new PlanningTrace(plan, sideVariablesTuple, aggregatorRecipe, callTrace); - - IndexerRecipe aggregatorIndexerRecipe = FACTORY.createAggregatorIndexerRecipe(); - aggregatorIndexerRecipe.setParent(aggregatorRecipe); - - int aggregatorWidth = sideVariablesTuple.size(); - int aggregateResultIndex = aggregatorWidth - 1; - - aggregatorIndexerRecipe.setMask(CompilerHelper.toRecipeMask(TupleMask.omit( - // aggregate according all but the last index - aggregateResultIndex, aggregatorWidth))); - PlanningTrace aggregatorIndexerTrace = new PlanningTrace(plan, sideVariablesTuple, aggregatorIndexerRecipe, - aggregatorTrace); - - JoinRecipe naturalJoinRecipe = FACTORY.createJoinRecipe(); - naturalJoinRecipe.setLeftParent((ProjectionIndexerRecipe) primaryIndexer.getRecipe()); - naturalJoinRecipe.setRightParent(aggregatorIndexerRecipe); - naturalJoinRecipe.setRightParentComplementaryMask(RecipesHelper.mask(aggregatorWidth, - // extend with last element only - the computation value - aggregateResultIndex)); - - // what if the new variable already has a value? - // even if already known, we add the new result variable, so that it can be filtered at the end - // boolean alreadyKnown = parentPlan.getVisibleVariables().contains(constraint.getResultVariable()); - - final List finalVariablesTuple = new ArrayList(parentCompiled.getVariablesTuple()); - finalVariablesTuple.add(constraint.getResultVariable()); - - PlanningTrace joinTrace = new PlanningTrace(plan, finalVariablesTuple, naturalJoinRecipe, primaryIndexer, - aggregatorIndexerTrace); - - return CompilerHelper.checkAndTrimEqualVariables(plan, joinTrace).cloneFor(plan); - // if (!alreadyKnown) { - // return joinTrace.cloneFor(plan); - // } else { - // //final Integer equalsWithIndex = parentCompiled.getPosMapping().get(parentCompiled.getVariablesTuple()); - // } - } - - private CompiledSubPlan compileDeferred(ExpressionEvaluation constraint, SubPlan plan, SubPlan parentPlan, - CompiledSubPlan parentCompiled) { - Map tupleNameMap = new HashMap(); - for (String name : constraint.getEvaluator().getInputParameterNames()) { - Map index = parentCompiled.getPosMapping(); - PVariable variable = constraint.getPSystem().getVariableByNameChecked(name); - Integer position = index.get(variable); - tupleNameMap.put(name, position); - } - - final PVariable outputVariable = constraint.getOutputVariable(); - final boolean booleanCheck = outputVariable == null; - - // TODO determine whether expression is costly - boolean cacheOutput = ReteHintOptions.cacheOutputOfEvaluatorsByDefault.getValueOrDefault(getHints(plan)); - // for (PAnnotation pAnnotation : - // plan.getBody().getPattern().getAnnotationsByName(EXPRESSION_EVALUATION_ANNOTATION"")) { - // for (Object value : pAnnotation.getAllValues("expensive")) { - // if (value instanceof Boolean) - // cacheOutput = (boolean) value; - // } - // } - - ExpressionEnforcerRecipe enforcerRecipe = booleanCheck ? FACTORY.createCheckRecipe() - : FACTORY.createEvalRecipe(); - enforcerRecipe.setParent(parentCompiled.getRecipe()); - enforcerRecipe.setExpression(RecipesHelper.expressionDefinition(constraint.getEvaluator())); - enforcerRecipe.setCacheOutput(cacheOutput); - if (enforcerRecipe instanceof EvalRecipe) { - ((EvalRecipe) enforcerRecipe).setUnwinding(constraint.isUnwinding()); - } - for (Entry entry : tupleNameMap.entrySet()) { - enforcerRecipe.getMappedIndices().put(entry.getKey(), entry.getValue()); - } - - final List enforcerVariablesTuple = new ArrayList(parentCompiled.getVariablesTuple()); - if (!booleanCheck) - enforcerVariablesTuple.add(outputVariable); - PlanningTrace enforcerTrace = new PlanningTrace(plan, enforcerVariablesTuple, enforcerRecipe, parentCompiled); - - return CompilerHelper.checkAndTrimEqualVariables(plan, enforcerTrace).cloneFor(plan); - } - - private CompiledSubPlan doCompileJoin(PJoin operation, SubPlan plan) { - final List compiledParents = getCompiledFormOfParents(plan); - final CompiledSubPlan leftCompiled = compiledParents.get(0); - final CompiledSubPlan rightCompiled = compiledParents.get(1); - - return compileToNaturalJoin(plan, leftCompiled, rightCompiled); - } - - private CompiledSubPlan compileToNaturalJoin(SubPlan plan, final PlanningTrace leftCompiled, - final PlanningTrace rightCompiled) { - // CHECK IF SPECIAL CASE - - // Is constant filtering applicable? - if (ReteHintOptions.useDiscriminatorDispatchersForConstantFiltering.getValueOrDefault(getHints(plan))) { - if (leftCompiled.getRecipe() instanceof ConstantRecipe - && rightCompiled.getVariablesTuple().containsAll(leftCompiled.getVariablesTuple())) { - return compileConstantFiltering(plan, rightCompiled, (ConstantRecipe) leftCompiled.getRecipe(), - leftCompiled.getVariablesTuple()); - } - if (rightCompiled.getRecipe() instanceof ConstantRecipe - && leftCompiled.getVariablesTuple().containsAll(rightCompiled.getVariablesTuple())) { - return compileConstantFiltering(plan, leftCompiled, (ConstantRecipe) rightCompiled.getRecipe(), - rightCompiled.getVariablesTuple()); - } - } - - // ELSE: ACTUAL JOIN - CompilerHelper.JoinHelper joinHelper = new CompilerHelper.JoinHelper(plan, leftCompiled, rightCompiled); - return new CompiledSubPlan(plan, joinHelper.getNaturalJoinVariablesTuple(), joinHelper.getNaturalJoinRecipe(), - joinHelper.getPrimaryIndexer(), joinHelper.getSecondaryIndexer()); - } - - private CompiledSubPlan doCompileProject(PProject operation, SubPlan plan) { - final List compiledParents = getCompiledFormOfParents(plan); - final CompiledSubPlan compiledParent = compiledParents.get(0); - - List projectedVariables = new ArrayList(operation.getToVariables()); - // Determinizing projection: try to keep original order (hopefully facilitates node reuse) - Map parentPosMapping = compiledParent.getPosMapping(); - Collections.sort(projectedVariables, Comparator.comparing(parentPosMapping::get)); - - return doProjectPlan(compiledParent, projectedVariables, true, - parentTrace -> parentTrace.cloneFor(plan), - (recipe, parentTrace) -> new PlanningTrace(plan, projectedVariables, recipe, parentTrace), - (recipe, parentTrace) -> new CompiledSubPlan(plan, projectedVariables, recipe, parentTrace) - ); - } - - /** - * Projects a subplan onto the specified variable tuple - * @param compiledParentPlan the compiled form of the subplan - * @param targetVariables list of variables to project to - * @param enforceUniqueness whether distinctness shall be enforced after the projection. - * Specify false only if directly connecting to a production node. - * @param reinterpretTraceFactory constructs a reinterpreted trace that simply relabels the compiled parent plan, in case it is sufficient - * @param intermediateTraceFactory constructs a recipe trace for an intermediate node, given the recipe of the node and its parent trace - * @param finalTraceFactory constructs a recipe trace for the final resulting node, given the recipe of the node and its parent trace - * @since 2.1 - */ - ResultTrace doProjectPlan( - final CompiledSubPlan compiledParentPlan, - final List targetVariables, - boolean enforceUniqueness, - Function reinterpretTraceFactory, - BiFunction intermediateTraceFactory, - BiFunction finalTraceFactory) - { - if (targetVariables.equals(compiledParentPlan.getVariablesTuple())) // no projection needed - return reinterpretTraceFactory.apply(compiledParentPlan); - - // otherwise, we need at least a trimmer - TrimmerRecipe trimmerRecipe = CompilerHelper.makeTrimmerRecipe(compiledParentPlan, targetVariables); - - // do we need to eliminate duplicates? - SubPlan parentPlan = compiledParentPlan.getSubPlan(); - if (!enforceUniqueness || BuildHelper.areAllVariablesDetermined( - parentPlan, - targetVariables, - queryAnalyzer, - true)) - { - // if uniqueness enforcess is unwanted or unneeeded, skip it - return finalTraceFactory.apply(trimmerRecipe, compiledParentPlan); - } else { - // add a uniqueness enforcer - UniquenessEnforcerRecipe recipe = FACTORY.createUniquenessEnforcerRecipe(); - recipe.getParents().add(trimmerRecipe); - - // temporary solution to support the deprecated option for now - final boolean deleteAndRederiveEvaluationDep = this.deleteAndRederiveEvaluation || ReteHintOptions.deleteRederiveEvaluation.getValueOrDefault(getHints(parentPlan)); - - recipe.setDeleteRederiveEvaluation(deleteAndRederiveEvaluationDep); - if (deleteAndRederiveEvaluationDep || (this.timelyEvaluation != null)) { - CompilerHelper.PosetTriplet triplet = CompilerHelper.computePosetInfo(targetVariables, parentPlan.getBody(), metaContext); - - if (triplet.comparator != null) { - MonotonicityInfo info = FACTORY.createMonotonicityInfo(); - info.setCoreMask(triplet.coreMask); - info.setPosetMask(triplet.posetMask); - info.setPosetComparator(triplet.comparator); - recipe.setOptionalMonotonicityInfo(info); - } - } - - RecipeTraceInfo trimmerTrace = intermediateTraceFactory.apply(trimmerRecipe, compiledParentPlan); - return finalTraceFactory.apply(recipe, trimmerTrace); - } - } - - /** - * Projects the final compiled form of a PBody onto the parameter tuple - * @param compiledBody the compiled form of the body, with all constraints enforced, not yet projected to query parameters - * @param enforceUniqueness whether distinctness shall be enforced after the projection. - * Specify false only if directly connecting to a production node. - * @since 2.1 - */ - RecipeTraceInfo projectBodyFinalToParameters( - final CompiledSubPlan compiledBody, - boolean enforceUniqueness) - { - final PBody body = compiledBody.getSubPlan().getBody(); - final List parameterList = body.getSymbolicParameterVariables(); - - return doProjectPlan(compiledBody, parameterList, enforceUniqueness, - parentTrace -> parentTrace, - (recipe, parentTrace) -> new ParameterProjectionTrace(body, recipe, parentTrace), - (recipe, parentTrace) -> new ParameterProjectionTrace(body, recipe, parentTrace) - ); - } - - private CompiledSubPlan doCompileStart(PStart operation, SubPlan plan) { - if (!operation.getAPrioriVariables().isEmpty()) { - throw new IllegalArgumentException("Input variables unsupported by Rete: " + plan.toShortString()); - } - final ConstantRecipe recipe = FACTORY.createConstantRecipe(); - recipe.getConstantValues().clear(); - - return new CompiledSubPlan(plan, new ArrayList(), recipe); - } - - private CompiledSubPlan doCompileEnumerate(EnumerablePConstraint constraint, SubPlan plan) { - final PlanningTrace trimmedTrace = doEnumerateAndDeduplicate(constraint, plan); - - return trimmedTrace.cloneFor(plan); - } - - private PlanningTrace doEnumerateAndDeduplicate(EnumerablePConstraint constraint, SubPlan plan) { - final PlanningTrace coreTrace = doEnumerateDispatch(plan, constraint); - final PlanningTrace trimmedTrace = CompilerHelper.checkAndTrimEqualVariables(plan, coreTrace); - return trimmedTrace; - } - - private PlanningTrace doEnumerateDispatch(SubPlan plan, EnumerablePConstraint constraint) { - if (constraint instanceof RelationEvaluation) { - return compileEnumerable(plan, (RelationEvaluation) constraint); - } else if (constraint instanceof BinaryTransitiveClosure) { - return compileEnumerable(plan, (BinaryTransitiveClosure) constraint); - } else if (constraint instanceof BinaryReflexiveTransitiveClosure) { - return compileEnumerable(plan, (BinaryReflexiveTransitiveClosure) constraint); + private final IQueryPlannerStrategy plannerStrategy; + private final IQueryMetaContext metaContext; + private final IQueryBackendHintProvider hintProvider; + private final PDisjunctionRewriter normalizer; + private final QueryAnalyzer queryAnalyzer; + private final Logger logger; + + /** + * @since 2.2 + */ + protected final boolean deleteAndRederiveEvaluation; + /** + * @since 2.4 + */ + protected final TimelyConfiguration timelyEvaluation; + + /** + * @since 1.5 + */ + public ReteRecipeCompiler(IQueryPlannerStrategy plannerStrategy, Logger logger, IQueryMetaContext metaContext, + IQueryCacheContext queryCacheContext, IQueryBackendHintProvider hintProvider, + QueryAnalyzer queryAnalyzer) { + this(plannerStrategy, logger, metaContext, queryCacheContext, hintProvider, queryAnalyzer, false, null); + } + + /** + * @since 2.4 + */ + public ReteRecipeCompiler(IQueryPlannerStrategy plannerStrategy, Logger logger, IQueryMetaContext metaContext, + IQueryCacheContext queryCacheContext, IQueryBackendHintProvider hintProvider, + QueryAnalyzer queryAnalyzer, + boolean deleteAndRederiveEvaluation, TimelyConfiguration timelyEvaluation) { + super(); + this.deleteAndRederiveEvaluation = deleteAndRederiveEvaluation; + this.timelyEvaluation = timelyEvaluation; + this.plannerStrategy = plannerStrategy; + this.logger = logger; + this.metaContext = metaContext; + this.queryAnalyzer = queryAnalyzer; + this.normalizer = new PDisjunctionRewriterCacher(new SurrogateQueryRewriter(), + new PBodyNormalizer(metaContext) { + + @Override + protected boolean shouldExpandWeakenedAlternatives(PQuery query) { + QueryEvaluationHint hint = ReteRecipeCompiler.this.hintProvider.getQueryEvaluationHint(query); + Boolean expandWeakenedAlternativeConstraints = + ReteHintOptions.expandWeakenedAlternativeConstraints + .getValueOrDefault(hint); + return expandWeakenedAlternativeConstraints; + } + + }); + this.hintProvider = hintProvider; + } + + static final RecipesFactory FACTORY = RecipesFactory.eINSTANCE; + + // INTERNALLY CACHED + private Map plannerCache = new HashMap(); + private Set planningInProgress = new HashSet(); + + private Map queryCompilerCache = new HashMap(); + private Set compilationInProgress = new HashSet(); + private IMultiLookup recursionCutoffPoints = + CollectionsFactory.createMultiLookup(Object.class, MemoryType.SETS, Object.class); + private Map subPlanCompilerCache = new HashMap(); + private Map compilerBackTrace = new HashMap(); + + /** + * Clears internal state + */ + public void reset() { + plannerCache.clear(); + planningInProgress.clear(); + queryCompilerCache.clear(); + subPlanCompilerCache.clear(); + compilerBackTrace.clear(); + } + + /** + * Returns a {@link CompiledQuery} compiled from a query + * + * @throws InterpreterRuntimeException + */ + public CompiledQuery getCompiledForm(PQuery query) { + CompiledQuery compiled = queryCompilerCache.get(query); + if (compiled == null) { + + IRewriterTraceCollector traceCollector = CommonQueryHintOptions.normalizationTraceCollector + .getValueOrDefault(hintProvider.getQueryEvaluationHint(query)); + if (traceCollector != null) { + traceCollector.addTrace(query, query); + } + + boolean reentrant = !compilationInProgress.add(query); + if (reentrant) { // oops, recursion into body in progress + RecursionCutoffPoint cutoffPoint = new RecursionCutoffPoint(query, getHints(query), metaContext, + deleteAndRederiveEvaluation, timelyEvaluation); + recursionCutoffPoints.addPair(query, cutoffPoint); + return cutoffPoint.getCompiledQuery(); + } else { // not reentrant, therefore no recursion, do the compilation + try { + compiled = compileProduction(query); + queryCompilerCache.put(query, compiled); + // backTrace.put(compiled.getRecipe(), plan); + + // if this was a recursive query, mend all points where recursion was cut off + for (RecursionCutoffPoint cutoffPoint : recursionCutoffPoints.lookupOrEmpty(query)) { + cutoffPoint.mend(compiled); + } + } finally { + compilationInProgress.remove(query); + } + } + } + return compiled; + } + + /** + * Returns a {@link CompiledSubPlan} compiled from a query plan + * + * @throws InterpreterRuntimeException + */ + public CompiledSubPlan getCompiledForm(SubPlan plan) { + CompiledSubPlan compiled = subPlanCompilerCache.get(plan); + if (compiled == null) { + compiled = doCompileDispatch(plan); + subPlanCompilerCache.put(plan, compiled); + compilerBackTrace.put(compiled.getRecipe(), plan); + } + return compiled; + } + + /** + * @throws InterpreterRuntimeException + */ + public SubPlan getPlan(PBody pBody) { + // if the query is not marked as being compiled, initiate compilation + // (this is useful in case of recursion if getPlan() is the entry point) + PQuery pQuery = pBody.getPattern(); + if (!compilationInProgress.contains(pQuery)) + getCompiledForm(pQuery); + + // Is the plan already cached? + SubPlan plan = plannerCache.get(pBody); + if (plan == null) { + boolean reentrant = !planningInProgress.add(pBody); + if (reentrant) { // oops, recursion into body in progress + throw new IllegalArgumentException( + "Planning-level recursion unsupported: " + pBody.getPattern().getFullyQualifiedName()); + } else { // not reentrant, therefore no recursion, do the planning + try { + plan = plannerStrategy.plan(pBody, logger, metaContext); + plannerCache.put(pBody, plan); + } finally { + planningInProgress.remove(pBody); + } + } + } + return plan; + } + + private CompiledQuery compileProduction(PQuery query) { + Collection bodyPlans = new ArrayList(); + normalizer.setTraceCollector(CommonQueryHintOptions.normalizationTraceCollector + .getValueOrDefault(hintProvider.getQueryEvaluationHint(query))); + for (PBody pBody : normalizer.rewrite(query).getBodies()) { + SubPlan bodyPlan = getPlan(pBody); + bodyPlans.add(bodyPlan); + } + return doCompileProduction(query, bodyPlans); + } + + private CompiledQuery doCompileProduction(PQuery query, Collection bodies) { + // TODO skip production node if there is just one body and no projection needed? + Map bodyFinalTraces = new HashMap(); + Collection bodyFinalRecipes = new HashSet(); + + for (SubPlan bodyFinalPlan : bodies) { + // skip over any projections at the end + bodyFinalPlan = BuildHelper.eliminateTrailingProjections(bodyFinalPlan); + + // TODO checkAndTrimEqualVariables may introduce superfluous trim, + // but whatever (no uniqueness enforcer needed) + + // compile body + final CompiledSubPlan compiledBody = getCompiledForm(bodyFinalPlan); + + // project to parameter list + RecipeTraceInfo finalTrace = projectBodyFinalToParameters(compiledBody, false); + + bodyFinalTraces.put(bodyFinalPlan.getBody(), finalTrace); + bodyFinalRecipes.add(finalTrace.getRecipe()); + } + + CompiledQuery compiled = CompilerHelper.makeQueryTrace(query, bodyFinalTraces, bodyFinalRecipes, + getHints(query), metaContext, deleteAndRederiveEvaluation, timelyEvaluation); + + return compiled; + } + + private CompiledSubPlan doCompileDispatch(SubPlan plan) { + final POperation operation = plan.getOperation(); + if (operation instanceof PEnumerate) { + return doCompileEnumerate(((PEnumerate) operation).getEnumerablePConstraint(), plan); + } else if (operation instanceof PApply) { + final PConstraint pConstraint = ((PApply) operation).getPConstraint(); + if (pConstraint instanceof EnumerablePConstraint) { + CompiledSubPlan primaryParent = getCompiledForm(plan.getParentPlans().get(0)); + PlanningTrace secondaryParent = doEnumerateDispatch(plan, (EnumerablePConstraint) pConstraint); + return compileToNaturalJoin(plan, primaryParent, secondaryParent); + } else if (pConstraint instanceof DeferredPConstraint) { + return doDeferredDispatch((DeferredPConstraint) pConstraint, plan); + } else { + throw new IllegalArgumentException("Unsupported PConstraint in query plan: " + plan.toShortString()); + } + } else if (operation instanceof PJoin) { + return doCompileJoin((PJoin) operation, plan); + } else if (operation instanceof PProject) { + return doCompileProject((PProject) operation, plan); + } else if (operation instanceof PStart) { + return doCompileStart((PStart) operation, plan); + } else { + throw new IllegalArgumentException("Unsupported POperation in query plan: " + plan.toShortString()); + } + } + + private CompiledSubPlan doDeferredDispatch(DeferredPConstraint constraint, SubPlan plan) { + final SubPlan parentPlan = plan.getParentPlans().get(0); + final CompiledSubPlan parentCompiled = getCompiledForm(parentPlan); + if (constraint instanceof Equality) { + return compileDeferred((Equality) constraint, plan, parentPlan, parentCompiled); + } else if (constraint instanceof ExportedParameter) { + return compileDeferred((ExportedParameter) constraint, plan, parentPlan, parentCompiled); + } else if (constraint instanceof Inequality) { + return compileDeferred((Inequality) constraint, plan, parentPlan, parentCompiled); + } else if (constraint instanceof NegativePatternCall) { + return compileDeferred((NegativePatternCall) constraint, plan, parentPlan, parentCompiled); + } else if (constraint instanceof PatternMatchCounter) { + return compileDeferred((PatternMatchCounter) constraint, plan, parentPlan, parentCompiled); + } else if (constraint instanceof AggregatorConstraint) { + return compileDeferred((AggregatorConstraint) constraint, plan, parentPlan, parentCompiled); + } else if (constraint instanceof LeftJoinConstraint leftJoinConstraint) { + return compileDeferred(leftJoinConstraint, plan, parentCompiled); + } else if (constraint instanceof ExpressionEvaluation) { + return compileDeferred((ExpressionEvaluation) constraint, plan, parentPlan, parentCompiled); + } else if (constraint instanceof TypeFilterConstraint) { + return compileDeferred((TypeFilterConstraint) constraint, plan, parentPlan, parentCompiled); + } + throw new UnsupportedOperationException("Unknown deferred constraint " + constraint); + } + + private CompiledSubPlan compileDeferred(Equality constraint, SubPlan plan, SubPlan parentPlan, + CompiledSubPlan parentCompiled) { + if (constraint.isMoot()) + return parentCompiled.cloneFor(plan); + + Integer index1 = parentCompiled.getPosMapping().get(constraint.getWho()); + Integer index2 = parentCompiled.getPosMapping().get(constraint.getWithWhom()); + + if (index1 != null && index2 != null && index1.intValue() != index2.intValue()) { + Integer indexLower = Math.min(index1, index2); + Integer indexHigher = Math.max(index1, index2); + + EqualityFilterRecipe equalityFilterRecipe = FACTORY.createEqualityFilterRecipe(); + equalityFilterRecipe.setParent(parentCompiled.getRecipe()); + equalityFilterRecipe.getIndices().add(indexLower); + equalityFilterRecipe.getIndices().add(indexHigher); + + return new CompiledSubPlan(plan, parentCompiled.getVariablesTuple(), equalityFilterRecipe, parentCompiled); + } else { + throw new IllegalArgumentException(String.format("Unable to interpret %s after compiled parent %s", + plan.toShortString(), parentCompiled.toString())); + } + } + + /** + * Precondition: constantTrace must map to a ConstantRecipe, and all of its variables must be contained in + * toFilterTrace. + */ + private CompiledSubPlan compileConstantFiltering(SubPlan plan, PlanningTrace toFilterTrace, + ConstantRecipe constantRecipe, List filteredVariables) { + PlanningTrace resultTrace = toFilterTrace; + + int constantVariablesSize = filteredVariables.size(); + for (int i = 0; i < constantVariablesSize; ++i) { + Object constantValue = constantRecipe.getConstantValues().get(i); + PVariable filteredVariable = filteredVariables.get(i); + int filteredColumn = resultTrace.getVariablesTuple().indexOf(filteredVariable); + + DiscriminatorDispatcherRecipe dispatcherRecipe = FACTORY.createDiscriminatorDispatcherRecipe(); + dispatcherRecipe.setDiscriminationColumnIndex(filteredColumn); + dispatcherRecipe.setParent(resultTrace.getRecipe()); + + PlanningTrace dispatcherTrace = new PlanningTrace(plan, resultTrace.getVariablesTuple(), dispatcherRecipe, + resultTrace); + + DiscriminatorBucketRecipe bucketRecipe = FACTORY.createDiscriminatorBucketRecipe(); + bucketRecipe.setBucketKey(constantValue); + bucketRecipe.setParent(dispatcherRecipe); + + PlanningTrace bucketTrace = new PlanningTrace(plan, dispatcherTrace.getVariablesTuple(), bucketRecipe, + dispatcherTrace); + + resultTrace = bucketTrace; + } + + return resultTrace.cloneFor(plan); + } + + private CompiledSubPlan compileDeferred(ExportedParameter constraint, SubPlan plan, SubPlan parentPlan, + CompiledSubPlan parentCompiled) { + return parentCompiled.cloneFor(plan); + } + + private CompiledSubPlan compileDeferred(Inequality constraint, SubPlan plan, SubPlan parentPlan, + CompiledSubPlan parentCompiled) { + if (constraint.isEliminable()) + return parentCompiled.cloneFor(plan); + + Integer index1 = parentCompiled.getPosMapping().get(constraint.getWho()); + Integer index2 = parentCompiled.getPosMapping().get(constraint.getWithWhom()); + + if (index1 != null && index2 != null && index1.intValue() != index2.intValue()) { + Integer indexLower = Math.min(index1, index2); + Integer indexHigher = Math.max(index1, index2); + + InequalityFilterRecipe inequalityFilterRecipe = FACTORY.createInequalityFilterRecipe(); + inequalityFilterRecipe.setParent(parentCompiled.getRecipe()); + inequalityFilterRecipe.setSubject(indexLower); + inequalityFilterRecipe.getInequals().add(indexHigher); + + return new CompiledSubPlan(plan, parentCompiled.getVariablesTuple(), inequalityFilterRecipe, + parentCompiled); + } else { + throw new IllegalArgumentException(String.format("Unable to interpret %s after compiled parent %s", + plan.toShortString(), parentCompiled.toString())); + } + } + + private CompiledSubPlan compileDeferred(TypeFilterConstraint constraint, SubPlan plan, SubPlan parentPlan, + CompiledSubPlan parentCompiled) { + final IInputKey inputKey = constraint.getInputKey(); + if (!metaContext.isStateless(inputKey)) + throw new UnsupportedOperationException( + "Non-enumerable input keys are currently supported in Rete only if they are stateless, unlike " + + inputKey); + + final Tuple constraintVariables = constraint.getVariablesTuple(); + final List parentVariables = parentCompiled.getVariablesTuple(); + + Mask mask; // select elements of the tuple to check against extensional relation + if (Tuples.flatTupleOf(parentVariables.toArray()).equals(constraintVariables)) { + mask = null; // lucky case, parent signature equals that of input key + } else { + List variables = new ArrayList(); + for (Object variable : constraintVariables.getElements()) { + variables.add((PVariable) variable); + } + mask = CompilerHelper.makeProjectionMask(parentCompiled, variables); + } + InputFilterRecipe inputFilterRecipe = RecipesHelper.inputFilterRecipe(parentCompiled.getRecipe(), inputKey, + inputKey.getStringID(), mask); + return new CompiledSubPlan(plan, parentVariables, inputFilterRecipe, parentCompiled); + } + + private CompiledSubPlan compileDeferred(NegativePatternCall constraint, SubPlan plan, SubPlan parentPlan, + CompiledSubPlan parentCompiled) { + final PlanningTrace callTrace = referQuery(constraint.getReferredQuery(), plan, + constraint.getActualParametersTuple()); + + CompilerHelper.JoinHelper joinHelper = new CompilerHelper.JoinHelper(plan, parentCompiled, callTrace); + final RecipeTraceInfo primaryIndexer = joinHelper.getPrimaryIndexer(); + final RecipeTraceInfo secondaryIndexer = joinHelper.getSecondaryIndexer(); + + AntiJoinRecipe antiJoinRecipe = FACTORY.createAntiJoinRecipe(); + antiJoinRecipe.setLeftParent((ProjectionIndexerRecipe) primaryIndexer.getRecipe()); + antiJoinRecipe.setRightParent((IndexerRecipe) secondaryIndexer.getRecipe()); + + return new CompiledSubPlan(plan, parentCompiled.getVariablesTuple(), antiJoinRecipe, primaryIndexer, + secondaryIndexer); + } + + private CompiledSubPlan compileDeferred(PatternMatchCounter constraint, SubPlan plan, SubPlan parentPlan, + CompiledSubPlan parentCompiled) { + final PlanningTrace callTrace = referQuery(constraint.getReferredQuery(), plan, + constraint.getActualParametersTuple()); + + // hack: use some mask computations (+ the indexers) from a fake natural join against the called query + CompilerHelper.JoinHelper fakeJoinHelper = new CompilerHelper.JoinHelper(plan, parentCompiled, callTrace); + final RecipeTraceInfo primaryIndexer = fakeJoinHelper.getPrimaryIndexer(); + final RecipeTraceInfo callProjectionIndexer = fakeJoinHelper.getSecondaryIndexer(); + + final List sideVariablesTuple = new ArrayList( + fakeJoinHelper.getSecondaryMask().transform(callTrace.getVariablesTuple())); + /* if (!booleanCheck) */ + sideVariablesTuple.add(constraint.getResultVariable()); + + CountAggregatorRecipe aggregatorRecipe = FACTORY.createCountAggregatorRecipe(); + aggregatorRecipe.setParent((ProjectionIndexerRecipe) callProjectionIndexer.getRecipe()); + PlanningTrace aggregatorTrace = new PlanningTrace(plan, sideVariablesTuple, aggregatorRecipe, + callProjectionIndexer); + + IndexerRecipe aggregatorIndexerRecipe = FACTORY.createAggregatorIndexerRecipe(); + aggregatorIndexerRecipe.setParent(aggregatorRecipe); + // aggregatorIndexerRecipe.setMask(RecipesHelper.mask( + // sideVariablesTuple.size(), + // //use same indices as in the projection indexer + // // EVEN if result variable already visible in left parent + // fakeJoinHelper.getSecondaryMask().indices + // )); + + int aggregatorWidth = sideVariablesTuple.size(); + int aggregateResultIndex = aggregatorWidth - 1; + + aggregatorIndexerRecipe.setMask(CompilerHelper.toRecipeMask(TupleMask.omit( + // aggregate according all but the last index + aggregateResultIndex, aggregatorWidth))); + PlanningTrace aggregatorIndexerTrace = new PlanningTrace(plan, sideVariablesTuple, aggregatorIndexerRecipe, + aggregatorTrace); + + JoinRecipe naturalJoinRecipe = FACTORY.createJoinRecipe(); + naturalJoinRecipe.setLeftParent((ProjectionIndexerRecipe) primaryIndexer.getRecipe()); + naturalJoinRecipe.setRightParent(aggregatorIndexerRecipe); + naturalJoinRecipe.setRightParentComplementaryMask(RecipesHelper.mask(aggregatorWidth, + // extend with last element only - the computation value + aggregateResultIndex)); + + // what if the new variable already has a value? + // even if already known, we add the new result variable, so that it can be filtered at the end + // boolean alreadyKnown = parentPlan.getVisibleVariables().contains(constraint.getResultVariable()); + + final List aggregatedVariablesTuple = new ArrayList(parentCompiled.getVariablesTuple()); + aggregatedVariablesTuple.add(constraint.getResultVariable()); + + PlanningTrace joinTrace = new PlanningTrace(plan, aggregatedVariablesTuple, naturalJoinRecipe, primaryIndexer, + aggregatorIndexerTrace); + + return CompilerHelper.checkAndTrimEqualVariables(plan, joinTrace).cloneFor(plan); + // if (!alreadyKnown) { + // return joinTrace.cloneFor(plan); + // } else { + // //final Integer equalsWithIndex = parentCompiled.getPosMapping().get(parentCompiled.getVariablesTuple()); + // } + } + + private CompiledSubPlan compileDeferred(AggregatorConstraint constraint, SubPlan plan, SubPlan parentPlan, + CompiledSubPlan parentCompiled) { + final PlanningTrace callTrace = referQuery(constraint.getReferredQuery(), plan, + constraint.getActualParametersTuple()); + + // hack: use some mask computations (+ the indexers) from a fake natural join against the called query + CompilerHelper.JoinHelper fakeJoinHelper = new CompilerHelper.JoinHelper(plan, parentCompiled, callTrace); + final RecipeTraceInfo primaryIndexer = fakeJoinHelper.getPrimaryIndexer(); + TupleMask callGroupMask = fakeJoinHelper.getSecondaryMask(); + + final List sideVariablesTuple = new ArrayList( + callGroupMask.transform(callTrace.getVariablesTuple())); + /* if (!booleanCheck) */ + sideVariablesTuple.add(constraint.getResultVariable()); + + IMultisetAggregationOperator operator = constraint.getAggregator().getOperator(); + + SingleColumnAggregatorRecipe columnAggregatorRecipe = FACTORY.createSingleColumnAggregatorRecipe(); + columnAggregatorRecipe.setParent(callTrace.getRecipe()); + columnAggregatorRecipe.setMultisetAggregationOperator(operator); + + int columnIndex = constraint.getAggregatedColumn(); + IPosetComparator posetComparator = null; + Mask groupMask = CompilerHelper.toRecipeMask(callGroupMask); + + // temporary solution to support the deprecated option for now + final boolean deleteAndRederiveEvaluationDep = + this.deleteAndRederiveEvaluation || ReteHintOptions.deleteRederiveEvaluation.getValueOrDefault(getHints(plan)); + + columnAggregatorRecipe.setDeleteRederiveEvaluation(deleteAndRederiveEvaluationDep); + if (deleteAndRederiveEvaluationDep || (this.timelyEvaluation != null)) { + List parameters = constraint.getReferredQuery().getParameters(); + IInputKey key = parameters.get(columnIndex).getDeclaredUnaryType(); + if (key != null && metaContext.isPosetKey(key)) { + posetComparator = metaContext.getPosetComparator(Collections.singleton(key)); + } + } + + if (posetComparator == null) { + columnAggregatorRecipe.setGroupByMask(groupMask); + columnAggregatorRecipe.setAggregableIndex(columnIndex); + } else { + MonotonicityInfo monotonicityInfo = FACTORY.createMonotonicityInfo(); + monotonicityInfo.setCoreMask(groupMask); + monotonicityInfo.setPosetMask(CompilerHelper.toRecipeMask( + TupleMask.selectSingle(columnIndex, constraint.getActualParametersTuple().getSize()))); + monotonicityInfo.setPosetComparator(posetComparator); + columnAggregatorRecipe.setOptionalMonotonicityInfo(monotonicityInfo); + } + + ReteNodeRecipe aggregatorRecipe = columnAggregatorRecipe; + PlanningTrace aggregatorTrace = new PlanningTrace(plan, sideVariablesTuple, aggregatorRecipe, callTrace); + + IndexerRecipe aggregatorIndexerRecipe = FACTORY.createAggregatorIndexerRecipe(); + aggregatorIndexerRecipe.setParent(aggregatorRecipe); + + int aggregatorWidth = sideVariablesTuple.size(); + int aggregateResultIndex = aggregatorWidth - 1; + + aggregatorIndexerRecipe.setMask(CompilerHelper.toRecipeMask(TupleMask.omit( + // aggregate according all but the last index + aggregateResultIndex, aggregatorWidth))); + PlanningTrace aggregatorIndexerTrace = new PlanningTrace(plan, sideVariablesTuple, aggregatorIndexerRecipe, + aggregatorTrace); + + JoinRecipe naturalJoinRecipe = FACTORY.createJoinRecipe(); + naturalJoinRecipe.setLeftParent((ProjectionIndexerRecipe) primaryIndexer.getRecipe()); + naturalJoinRecipe.setRightParent(aggregatorIndexerRecipe); + naturalJoinRecipe.setRightParentComplementaryMask(RecipesHelper.mask(aggregatorWidth, + // extend with last element only - the computation value + aggregateResultIndex)); + + // what if the new variable already has a value? + // even if already known, we add the new result variable, so that it can be filtered at the end + // boolean alreadyKnown = parentPlan.getVisibleVariables().contains(constraint.getResultVariable()); + + final List finalVariablesTuple = new ArrayList(parentCompiled.getVariablesTuple()); + finalVariablesTuple.add(constraint.getResultVariable()); + + PlanningTrace joinTrace = new PlanningTrace(plan, finalVariablesTuple, naturalJoinRecipe, primaryIndexer, + aggregatorIndexerTrace); + + return CompilerHelper.checkAndTrimEqualVariables(plan, joinTrace).cloneFor(plan); + // if (!alreadyKnown) { + // return joinTrace.cloneFor(plan); + // } else { + // //final Integer equalsWithIndex = parentCompiled.getPosMapping().get(parentCompiled.getVariablesTuple()); + // } + } + + private CompiledSubPlan compileDeferred(LeftJoinConstraint constraint, SubPlan plan, + CompiledSubPlan parentCompiled) { + var callTrace = referQuery(constraint.getReferredQuery(), plan, constraint.getActualParametersTuple()); + var fakeJoinHelper = new CompilerHelper.JoinHelper(plan, parentCompiled, callTrace); + var primaryIndexer = fakeJoinHelper.getPrimaryIndexer(); + var secondaryIndexer = fakeJoinHelper.getSecondaryIndexer(); + + var sideVariablesTuple = CompilerHelper.convertVariablesTuple(constraint.getActualParametersTuple()); + var resultVariable = constraint.getResultVariable(); + sideVariablesTuple.set(constraint.getOptionalColumn(), resultVariable); + + var leftNodeRecipe = FACTORY.createOuterJoinNodeRecipe(); + var secondaryIndexerRecipe = (ProjectionIndexerRecipe) secondaryIndexer.getRecipe(); + leftNodeRecipe.setParent(secondaryIndexerRecipe); + leftNodeRecipe.setDefaultValue(constraint.getDefaultValue()); + var leftNodeTrace = new PlanningTrace(plan, sideVariablesTuple, leftNodeRecipe, secondaryIndexer); + + var leftIndexerRecipe = FACTORY.createOuterJoinIndexerRecipe(); + leftIndexerRecipe.setParent(leftIndexerRecipe); + // Must make a copy of the mask here, because we are already using secondaryIndexerRecipe in the plan an mask + // is a containment reference. + var copyOfMask = EcoreUtil.copy(secondaryIndexerRecipe.getMask()); + leftIndexerRecipe.setMask(copyOfMask); + var leftIndexerTrace = new PlanningTrace(plan, sideVariablesTuple, leftIndexerRecipe, leftNodeTrace); + + var naturalJoinRecipe = FACTORY.createJoinRecipe(); + naturalJoinRecipe.setLeftParent((ProjectionIndexerRecipe) primaryIndexer.getRecipe()); + naturalJoinRecipe.setRightParent(leftIndexerRecipe); + var complementaryMask = fakeJoinHelper.getNaturalJoinRecipe().getRightParentComplementaryMask(); + naturalJoinRecipe.setRightParentComplementaryMask(complementaryMask); + + var primaryVariablesTuple = parentCompiled.getVariablesTuple(); + var joinedVariablesTuple = new ArrayList(primaryVariablesTuple.size() + 1); + joinedVariablesTuple.addAll(primaryVariablesTuple); + joinedVariablesTuple.add(resultVariable); + var joinTrace = new PlanningTrace(plan, joinedVariablesTuple, naturalJoinRecipe, primaryIndexer, + leftIndexerTrace); + + return CompilerHelper.checkAndTrimEqualVariables(plan, joinTrace).cloneFor(plan); + } + + private CompiledSubPlan compileDeferred(ExpressionEvaluation constraint, SubPlan plan, SubPlan parentPlan, + CompiledSubPlan parentCompiled) { + Map tupleNameMap = new HashMap(); + for (String name : constraint.getEvaluator().getInputParameterNames()) { + Map index = parentCompiled.getPosMapping(); + PVariable variable = constraint.getPSystem().getVariableByNameChecked(name); + Integer position = index.get(variable); + tupleNameMap.put(name, position); + } + + final PVariable outputVariable = constraint.getOutputVariable(); + final boolean booleanCheck = outputVariable == null; + + // TODO determine whether expression is costly + boolean cacheOutput = ReteHintOptions.cacheOutputOfEvaluatorsByDefault.getValueOrDefault(getHints(plan)); + // for (PAnnotation pAnnotation : + // plan.getBody().getPattern().getAnnotationsByName(EXPRESSION_EVALUATION_ANNOTATION"")) { + // for (Object value : pAnnotation.getAllValues("expensive")) { + // if (value instanceof Boolean) + // cacheOutput = (boolean) value; + // } + // } + + ExpressionEnforcerRecipe enforcerRecipe = booleanCheck ? FACTORY.createCheckRecipe() + : FACTORY.createEvalRecipe(); + enforcerRecipe.setParent(parentCompiled.getRecipe()); + enforcerRecipe.setExpression(RecipesHelper.expressionDefinition(constraint.getEvaluator())); + enforcerRecipe.setCacheOutput(cacheOutput); + if (enforcerRecipe instanceof EvalRecipe) { + ((EvalRecipe) enforcerRecipe).setUnwinding(constraint.isUnwinding()); + } + for (Entry entry : tupleNameMap.entrySet()) { + enforcerRecipe.getMappedIndices().put(entry.getKey(), entry.getValue()); + } + + final List enforcerVariablesTuple = new ArrayList(parentCompiled.getVariablesTuple()); + if (!booleanCheck) + enforcerVariablesTuple.add(outputVariable); + PlanningTrace enforcerTrace = new PlanningTrace(plan, enforcerVariablesTuple, enforcerRecipe, parentCompiled); + + return CompilerHelper.checkAndTrimEqualVariables(plan, enforcerTrace).cloneFor(plan); + } + + private CompiledSubPlan doCompileJoin(PJoin operation, SubPlan plan) { + final List compiledParents = getCompiledFormOfParents(plan); + final CompiledSubPlan leftCompiled = compiledParents.get(0); + final CompiledSubPlan rightCompiled = compiledParents.get(1); + + return compileToNaturalJoin(plan, leftCompiled, rightCompiled); + } + + private CompiledSubPlan compileToNaturalJoin(SubPlan plan, final PlanningTrace leftCompiled, + final PlanningTrace rightCompiled) { + // CHECK IF SPECIAL CASE + + // Is constant filtering applicable? + if (ReteHintOptions.useDiscriminatorDispatchersForConstantFiltering.getValueOrDefault(getHints(plan))) { + if (leftCompiled.getRecipe() instanceof ConstantRecipe + && rightCompiled.getVariablesTuple().containsAll(leftCompiled.getVariablesTuple())) { + return compileConstantFiltering(plan, rightCompiled, (ConstantRecipe) leftCompiled.getRecipe(), + leftCompiled.getVariablesTuple()); + } + if (rightCompiled.getRecipe() instanceof ConstantRecipe + && leftCompiled.getVariablesTuple().containsAll(rightCompiled.getVariablesTuple())) { + return compileConstantFiltering(plan, leftCompiled, (ConstantRecipe) rightCompiled.getRecipe(), + rightCompiled.getVariablesTuple()); + } + } + + // ELSE: ACTUAL JOIN + CompilerHelper.JoinHelper joinHelper = new CompilerHelper.JoinHelper(plan, leftCompiled, rightCompiled); + return new CompiledSubPlan(plan, joinHelper.getNaturalJoinVariablesTuple(), joinHelper.getNaturalJoinRecipe(), + joinHelper.getPrimaryIndexer(), joinHelper.getSecondaryIndexer()); + } + + private CompiledSubPlan doCompileProject(PProject operation, SubPlan plan) { + final List compiledParents = getCompiledFormOfParents(plan); + final CompiledSubPlan compiledParent = compiledParents.get(0); + + List projectedVariables = new ArrayList(operation.getToVariables()); + // Determinizing projection: try to keep original order (hopefully facilitates node reuse) + Map parentPosMapping = compiledParent.getPosMapping(); + Collections.sort(projectedVariables, Comparator.comparing(parentPosMapping::get)); + + return doProjectPlan(compiledParent, projectedVariables, true, + parentTrace -> parentTrace.cloneFor(plan), + (recipe, parentTrace) -> new PlanningTrace(plan, projectedVariables, recipe, parentTrace), + (recipe, parentTrace) -> new CompiledSubPlan(plan, projectedVariables, recipe, parentTrace) + ); + } + + /** + * Projects a subplan onto the specified variable tuple + * + * @param compiledParentPlan the compiled form of the subplan + * @param targetVariables list of variables to project to + * @param enforceUniqueness whether distinctness shall be enforced after the projection. + * Specify false only if directly connecting to a production node. + * @param reinterpretTraceFactory constructs a reinterpreted trace that simply relabels the compiled parent plan, + * in case it is sufficient + * @param intermediateTraceFactory constructs a recipe trace for an intermediate node, given the recipe of the + * node and its parent trace + * @param finalTraceFactory constructs a recipe trace for the final resulting node, given the recipe of the + * node and its parent trace + * @since 2.1 + */ + ResultTrace doProjectPlan( + final CompiledSubPlan compiledParentPlan, + final List targetVariables, + boolean enforceUniqueness, + Function reinterpretTraceFactory, + BiFunction intermediateTraceFactory, + BiFunction finalTraceFactory) { + if (targetVariables.equals(compiledParentPlan.getVariablesTuple())) // no projection needed + return reinterpretTraceFactory.apply(compiledParentPlan); + + // otherwise, we need at least a trimmer + TrimmerRecipe trimmerRecipe = CompilerHelper.makeTrimmerRecipe(compiledParentPlan, targetVariables); + + // do we need to eliminate duplicates? + SubPlan parentPlan = compiledParentPlan.getSubPlan(); + if (!enforceUniqueness || BuildHelper.areAllVariablesDetermined( + parentPlan, + targetVariables, + queryAnalyzer, + true)) { + // if uniqueness enforcess is unwanted or unneeeded, skip it + return finalTraceFactory.apply(trimmerRecipe, compiledParentPlan); + } else { + // add a uniqueness enforcer + UniquenessEnforcerRecipe recipe = FACTORY.createUniquenessEnforcerRecipe(); + recipe.getParents().add(trimmerRecipe); + + // temporary solution to support the deprecated option for now + final boolean deleteAndRederiveEvaluationDep = + this.deleteAndRederiveEvaluation || ReteHintOptions.deleteRederiveEvaluation.getValueOrDefault(getHints(parentPlan)); + + recipe.setDeleteRederiveEvaluation(deleteAndRederiveEvaluationDep); + if (deleteAndRederiveEvaluationDep || (this.timelyEvaluation != null)) { + CompilerHelper.PosetTriplet triplet = CompilerHelper.computePosetInfo(targetVariables, + parentPlan.getBody(), metaContext); + + if (triplet.comparator != null) { + MonotonicityInfo info = FACTORY.createMonotonicityInfo(); + info.setCoreMask(triplet.coreMask); + info.setPosetMask(triplet.posetMask); + info.setPosetComparator(triplet.comparator); + recipe.setOptionalMonotonicityInfo(info); + } + } + + RecipeTraceInfo trimmerTrace = intermediateTraceFactory.apply(trimmerRecipe, compiledParentPlan); + return finalTraceFactory.apply(recipe, trimmerTrace); + } + } + + /** + * Projects the final compiled form of a PBody onto the parameter tuple + * + * @param compiledBody the compiled form of the body, with all constraints enforced, not yet projected to + * query parameters + * @param enforceUniqueness whether distinctness shall be enforced after the projection. + * Specify false only if directly connecting to a production node. + * @since 2.1 + */ + RecipeTraceInfo projectBodyFinalToParameters( + final CompiledSubPlan compiledBody, + boolean enforceUniqueness) { + final PBody body = compiledBody.getSubPlan().getBody(); + final List parameterList = body.getSymbolicParameterVariables(); + + return doProjectPlan(compiledBody, parameterList, enforceUniqueness, + parentTrace -> parentTrace, + (recipe, parentTrace) -> new ParameterProjectionTrace(body, recipe, parentTrace), + (recipe, parentTrace) -> new ParameterProjectionTrace(body, recipe, parentTrace) + ); + } + + private CompiledSubPlan doCompileStart(PStart operation, SubPlan plan) { + if (!operation.getAPrioriVariables().isEmpty()) { + throw new IllegalArgumentException("Input variables unsupported by Rete: " + plan.toShortString()); + } + final ConstantRecipe recipe = FACTORY.createConstantRecipe(); + recipe.getConstantValues().clear(); + + return new CompiledSubPlan(plan, new ArrayList(), recipe); + } + + private CompiledSubPlan doCompileEnumerate(EnumerablePConstraint constraint, SubPlan plan) { + final PlanningTrace trimmedTrace = doEnumerateAndDeduplicate(constraint, plan); + + return trimmedTrace.cloneFor(plan); + } + + private PlanningTrace doEnumerateAndDeduplicate(EnumerablePConstraint constraint, SubPlan plan) { + final PlanningTrace coreTrace = doEnumerateDispatch(plan, constraint); + final PlanningTrace trimmedTrace = CompilerHelper.checkAndTrimEqualVariables(plan, coreTrace); + return trimmedTrace; + } + + private PlanningTrace doEnumerateDispatch(SubPlan plan, EnumerablePConstraint constraint) { + if (constraint instanceof RelationEvaluation) { + return compileEnumerable(plan, (RelationEvaluation) constraint); + } else if (constraint instanceof BinaryTransitiveClosure) { + return compileEnumerable(plan, (BinaryTransitiveClosure) constraint); + } else if (constraint instanceof BinaryReflexiveTransitiveClosure) { + return compileEnumerable(plan, (BinaryReflexiveTransitiveClosure) constraint); } else if (constraint instanceof RepresentativeElectionConstraint) { return compileEnumerable(plan, (RepresentativeElectionConstraint) constraint); - } else if (constraint instanceof ConstantValue) { - return compileEnumerable(plan, (ConstantValue) constraint); - } else if (constraint instanceof PositivePatternCall) { - return compileEnumerable(plan, (PositivePatternCall) constraint); - } else if (constraint instanceof TypeConstraint) { - return compileEnumerable(plan, (TypeConstraint) constraint); - } - throw new UnsupportedOperationException("Unknown enumerable constraint " + constraint); - } - - private PlanningTrace compileEnumerable(SubPlan plan, BinaryReflexiveTransitiveClosure constraint) { - // TODO the implementation would perform better if an inequality check would be used after tcRecipe and - // uniqueness enforcer be replaced by a transparent node with multiple parents, but such a node is not available - // in recipe metamodel in VIATRA 2.0 - - // Find called query - final PQuery referredQuery = constraint.getSupplierKey(); - final PlanningTrace callTrace = referQuery(referredQuery, plan, constraint.getVariablesTuple()); - - // Calculate irreflexive transitive closure - final TransitiveClosureRecipe tcRecipe = FACTORY.createTransitiveClosureRecipe(); - tcRecipe.setParent(callTrace.getRecipe()); - final PlanningTrace tcTrace = new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), tcRecipe, callTrace); - - // Enumerate universe type - final IInputKey inputKey = constraint.getUniverseType(); - final InputRecipe universeTypeRecipe = RecipesHelper.inputRecipe(inputKey, inputKey.getStringID(), inputKey.getArity()); - final PlanningTrace universeTypeTrace = new PlanningTrace(plan, CompilerHelper.convertVariablesTuple( - Tuples.staticArityFlatTupleOf(constraint.getVariablesTuple().get(0))), universeTypeRecipe); - - // Calculate reflexive access by duplicating universe type column - final TrimmerRecipe reflexiveRecipe = FACTORY.createTrimmerRecipe(); - reflexiveRecipe.setMask(RecipesHelper.mask(1, 0, 0)); - reflexiveRecipe.setParent(universeTypeRecipe); - final PlanningTrace reflexiveTrace = new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), reflexiveRecipe, universeTypeTrace); - - // Finally, reduce duplicates after a join - final UniquenessEnforcerRecipe brtcRecipe = FACTORY.createUniquenessEnforcerRecipe(); - brtcRecipe.getParents().add(tcRecipe); - brtcRecipe.getParents().add(reflexiveRecipe); - - return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), brtcRecipe, reflexiveTrace, tcTrace); - } + } else if (constraint instanceof ConstantValue) { + return compileEnumerable(plan, (ConstantValue) constraint); + } else if (constraint instanceof PositivePatternCall) { + return compileEnumerable(plan, (PositivePatternCall) constraint); + } else if (constraint instanceof TypeConstraint) { + return compileEnumerable(plan, (TypeConstraint) constraint); + } + throw new UnsupportedOperationException("Unknown enumerable constraint " + constraint); + } + + private PlanningTrace compileEnumerable(SubPlan plan, BinaryReflexiveTransitiveClosure constraint) { + // TODO the implementation would perform better if an inequality check would be used after tcRecipe and + // uniqueness enforcer be replaced by a transparent node with multiple parents, but such a node is not + // available + // in recipe metamodel in VIATRA 2.0 + + // Find called query + final PQuery referredQuery = constraint.getSupplierKey(); + final PlanningTrace callTrace = referQuery(referredQuery, plan, constraint.getVariablesTuple()); + + // Calculate irreflexive transitive closure + final TransitiveClosureRecipe tcRecipe = FACTORY.createTransitiveClosureRecipe(); + tcRecipe.setParent(callTrace.getRecipe()); + final PlanningTrace tcTrace = new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), + tcRecipe, callTrace); + + // Enumerate universe type + final IInputKey inputKey = constraint.getUniverseType(); + final InputRecipe universeTypeRecipe = RecipesHelper.inputRecipe(inputKey, inputKey.getStringID(), + inputKey.getArity()); + final PlanningTrace universeTypeTrace = new PlanningTrace(plan, CompilerHelper.convertVariablesTuple( + Tuples.staticArityFlatTupleOf(constraint.getVariablesTuple().get(0))), universeTypeRecipe); + + // Calculate reflexive access by duplicating universe type column + final TrimmerRecipe reflexiveRecipe = FACTORY.createTrimmerRecipe(); + reflexiveRecipe.setMask(RecipesHelper.mask(1, 0, 0)); + reflexiveRecipe.setParent(universeTypeRecipe); + final PlanningTrace reflexiveTrace = new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), + reflexiveRecipe, universeTypeTrace); + + // Finally, reduce duplicates after a join + final UniquenessEnforcerRecipe brtcRecipe = FACTORY.createUniquenessEnforcerRecipe(); + brtcRecipe.getParents().add(tcRecipe); + brtcRecipe.getParents().add(reflexiveRecipe); + + return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), brtcRecipe, reflexiveTrace, + tcTrace); + } private PlanningTrace compileEnumerable(SubPlan plan, RepresentativeElectionConstraint constraint) { var referredQuery = constraint.getSupplierKey(); @@ -839,109 +901,110 @@ public class ReteRecipeCompiler { return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), recipe, callTrace); } - private PlanningTrace compileEnumerable(SubPlan plan, BinaryTransitiveClosure constraint) { - final PQuery referredQuery = constraint.getSupplierKey(); - final PlanningTrace callTrace = referQuery(referredQuery, plan, constraint.getVariablesTuple()); - - final TransitiveClosureRecipe recipe = FACTORY.createTransitiveClosureRecipe(); - recipe.setParent(callTrace.getRecipe()); - - return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), recipe, callTrace); - } - - private PlanningTrace compileEnumerable(SubPlan plan, RelationEvaluation constraint) { - final List parentRecipes = new ArrayList(); - final List parentTraceInfos = new ArrayList(); - for (final PQuery inputQuery : constraint.getReferredQueries()) { - final CompiledQuery compiledQuery = getCompiledForm(inputQuery); - parentRecipes.add(compiledQuery.getRecipe()); - parentTraceInfos.add(compiledQuery); - } - final RelationEvaluationRecipe recipe = FACTORY.createRelationEvaluationRecipe(); - recipe.getParents().addAll(parentRecipes); - recipe.setEvaluator(RecipesHelper.expressionDefinition(constraint.getEvaluator())); - return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), recipe, parentTraceInfos); - } - - private PlanningTrace compileEnumerable(SubPlan plan, PositivePatternCall constraint) { - final PQuery referredQuery = constraint.getReferredQuery(); - return referQuery(referredQuery, plan, constraint.getVariablesTuple()); - } - - private PlanningTrace compileEnumerable(SubPlan plan, TypeConstraint constraint) { - final IInputKey inputKey = constraint.getSupplierKey(); - final InputRecipe recipe = RecipesHelper.inputRecipe(inputKey, inputKey.getStringID(), inputKey.getArity()); - return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), recipe); - } - - private PlanningTrace compileEnumerable(SubPlan plan, ConstantValue constraint) { - final ConstantRecipe recipe = FACTORY.createConstantRecipe(); - recipe.getConstantValues().add(constraint.getSupplierKey()); - return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), recipe); - } - - // TODO handle recursion - private PlanningTrace referQuery(PQuery query, SubPlan plan, Tuple actualParametersTuple) { - RecipeTraceInfo referredQueryTrace = originalTraceOfReferredQuery(query); - return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(actualParametersTuple), - referredQueryTrace.getRecipe(), referredQueryTrace.getParentRecipeTracesForCloning()); - } - - private RecipeTraceInfo originalTraceOfReferredQuery(PQuery query) { - // eliminate superfluous production node? - if (PVisibility.EMBEDDED == query.getVisibility()) { // currently inline patterns only - Set rewrittenBodies = normalizer.rewrite(query).getBodies(); - if (1 == rewrittenBodies.size()) { // non-disjunctive - // TODO in the future, check if non-recursive - (not currently permitted) - - PBody pBody = rewrittenBodies.iterator().next(); - SubPlan bodyFinalPlan = getPlan(pBody); - - // skip over any projections at the end - bodyFinalPlan = BuildHelper.eliminateTrailingProjections(bodyFinalPlan); - - // TODO checkAndTrimEqualVariables may introduce superfluous trim, - // but whatever (no uniqueness enforcer needed) - - // compile body - final CompiledSubPlan compiledBody = getCompiledForm(bodyFinalPlan); - - // project to parameter list, add uniqueness enforcer if necessary - return projectBodyFinalToParameters(compiledBody, true /* ensure uniqueness, as no production node is used */); - } - } - - // otherwise, regular reference to recipe realizing the query - return getCompiledForm(query); - } - - protected List getCompiledFormOfParents(SubPlan plan) { - List results = new ArrayList(); - for (SubPlan parentPlan : plan.getParentPlans()) { - results.add(getCompiledForm(parentPlan)); - } - return results; - } - - /** - * Returns an unmodifiable view of currently cached compiled queries. - */ - public Map getCachedCompiledQueries() { - return Collections.unmodifiableMap(queryCompilerCache); - } - - /** - * Returns an unmodifiable view of currently cached query plans. - */ - public Map getCachedQueryPlans() { - return Collections.unmodifiableMap(plannerCache); - } - - private QueryEvaluationHint getHints(SubPlan plan) { - return getHints(plan.getBody().getPattern()); - } - - private QueryEvaluationHint getHints(PQuery pattern) { - return hintProvider.getQueryEvaluationHint(pattern); - } + private PlanningTrace compileEnumerable(SubPlan plan, BinaryTransitiveClosure constraint) { + final PQuery referredQuery = constraint.getSupplierKey(); + final PlanningTrace callTrace = referQuery(referredQuery, plan, constraint.getVariablesTuple()); + + final TransitiveClosureRecipe recipe = FACTORY.createTransitiveClosureRecipe(); + recipe.setParent(callTrace.getRecipe()); + + return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), recipe, callTrace); + } + + private PlanningTrace compileEnumerable(SubPlan plan, RelationEvaluation constraint) { + final List parentRecipes = new ArrayList(); + final List parentTraceInfos = new ArrayList(); + for (final PQuery inputQuery : constraint.getReferredQueries()) { + final CompiledQuery compiledQuery = getCompiledForm(inputQuery); + parentRecipes.add(compiledQuery.getRecipe()); + parentTraceInfos.add(compiledQuery); + } + final RelationEvaluationRecipe recipe = FACTORY.createRelationEvaluationRecipe(); + recipe.getParents().addAll(parentRecipes); + recipe.setEvaluator(RecipesHelper.expressionDefinition(constraint.getEvaluator())); + return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), recipe, parentTraceInfos); + } + + private PlanningTrace compileEnumerable(SubPlan plan, PositivePatternCall constraint) { + final PQuery referredQuery = constraint.getReferredQuery(); + return referQuery(referredQuery, plan, constraint.getVariablesTuple()); + } + + private PlanningTrace compileEnumerable(SubPlan plan, TypeConstraint constraint) { + final IInputKey inputKey = constraint.getSupplierKey(); + final InputRecipe recipe = RecipesHelper.inputRecipe(inputKey, inputKey.getStringID(), inputKey.getArity()); + return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), recipe); + } + + private PlanningTrace compileEnumerable(SubPlan plan, ConstantValue constraint) { + final ConstantRecipe recipe = FACTORY.createConstantRecipe(); + recipe.getConstantValues().add(constraint.getSupplierKey()); + return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(constraint), recipe); + } + + // TODO handle recursion + private PlanningTrace referQuery(PQuery query, SubPlan plan, Tuple actualParametersTuple) { + RecipeTraceInfo referredQueryTrace = originalTraceOfReferredQuery(query); + return new PlanningTrace(plan, CompilerHelper.convertVariablesTuple(actualParametersTuple), + referredQueryTrace.getRecipe(), referredQueryTrace.getParentRecipeTracesForCloning()); + } + + private RecipeTraceInfo originalTraceOfReferredQuery(PQuery query) { + // eliminate superfluous production node? + if (PVisibility.EMBEDDED == query.getVisibility()) { // currently inline patterns only + Set rewrittenBodies = normalizer.rewrite(query).getBodies(); + if (1 == rewrittenBodies.size()) { // non-disjunctive + // TODO in the future, check if non-recursive - (not currently permitted) + + PBody pBody = rewrittenBodies.iterator().next(); + SubPlan bodyFinalPlan = getPlan(pBody); + + // skip over any projections at the end + bodyFinalPlan = BuildHelper.eliminateTrailingProjections(bodyFinalPlan); + + // TODO checkAndTrimEqualVariables may introduce superfluous trim, + // but whatever (no uniqueness enforcer needed) + + // compile body + final CompiledSubPlan compiledBody = getCompiledForm(bodyFinalPlan); + + // project to parameter list, add uniqueness enforcer if necessary + return projectBodyFinalToParameters(compiledBody, true /* ensure uniqueness, as no production node is + used */); + } + } + + // otherwise, regular reference to recipe realizing the query + return getCompiledForm(query); + } + + protected List getCompiledFormOfParents(SubPlan plan) { + List results = new ArrayList(); + for (SubPlan parentPlan : plan.getParentPlans()) { + results.add(getCompiledForm(parentPlan)); + } + return results; + } + + /** + * Returns an unmodifiable view of currently cached compiled queries. + */ + public Map getCachedCompiledQueries() { + return Collections.unmodifiableMap(queryCompilerCache); + } + + /** + * Returns an unmodifiable view of currently cached query plans. + */ + public Map getCachedQueryPlans() { + return Collections.unmodifiableMap(plannerCache); + } + + private QueryEvaluationHint getHints(SubPlan plan) { + return getHints(plan.getBody().getPattern()); + } + + private QueryEvaluationHint getHints(PQuery pattern) { + return hintProvider.getQueryEvaluationHint(pattern); + } } diff --git a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/network/ConnectionFactory.java b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/network/ConnectionFactory.java index c69757b6..fe70cbc3 100644 --- a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/network/ConnectionFactory.java +++ b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/network/ConnectionFactory.java @@ -11,6 +11,7 @@ package tools.refinery.interpreter.rete.network; import tools.refinery.interpreter.matchers.tuple.Tuple; import tools.refinery.interpreter.rete.aggregation.IndexerBasedAggregatorNode; +import tools.refinery.interpreter.rete.aggregation.LeftJoinNode; import tools.refinery.interpreter.rete.boundary.InputConnector; import tools.refinery.interpreter.rete.eval.RelationEvaluatorNode; import tools.refinery.interpreter.rete.index.DualInputNode; @@ -78,9 +79,12 @@ class ConnectionFactory { Slots slots = avoidActiveNodeConflict(parentTraces.get(0), parentTraces.get(1)); beta.connectToIndexers(slots.primary, slots.secondary); } else if (recipe instanceof IndexerBasedAggregatorRecipe) { - final IndexerBasedAggregatorNode aggregator = (IndexerBasedAggregatorNode) freshNode; - final IndexerBasedAggregatorRecipe aggregatorRecipe = (IndexerBasedAggregatorRecipe) recipe; - aggregator.initializeWith((ProjectionIndexer) resolveIndexer(aggregatorRecipe.getParent())); + final IndexerBasedAggregatorNode aggregator = (IndexerBasedAggregatorNode) freshNode; + final IndexerBasedAggregatorRecipe aggregatorRecipe = (IndexerBasedAggregatorRecipe) recipe; + aggregator.initializeWith((ProjectionIndexer) resolveIndexer(aggregatorRecipe.getParent())); + } else if (recipe instanceof OuterJoinNodeRecipe outerJoinNodeRecipe) { + var leftJoinNode = (LeftJoinNode) freshNode; + leftJoinNode.initializeWith((ProjectionIndexer) resolveIndexer(outerJoinNodeRecipe.getParent())); } else if (recipe instanceof MultiParentNodeRecipe) { final Receiver receiver = (Receiver) freshNode; List parentRecipes = ((MultiParentNodeRecipe) recipe).getParents(); diff --git a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/network/NodeFactory.java b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/network/NodeFactory.java index 301b757d..1f6a01ae 100644 --- a/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/network/NodeFactory.java +++ b/subprojects/interpreter-rete/src/main/java/tools/refinery/interpreter/rete/network/NodeFactory.java @@ -20,6 +20,7 @@ import tools.refinery.interpreter.matchers.tuple.Tuples; import tools.refinery.interpreter.rete.aggregation.ColumnAggregatorNode; import tools.refinery.interpreter.rete.aggregation.CountNode; import tools.refinery.interpreter.rete.aggregation.IAggregatorNode; +import tools.refinery.interpreter.rete.aggregation.LeftJoinNode; import tools.refinery.interpreter.rete.aggregation.timely.FaithfulParallelTimelyColumnAggregatorNode; import tools.refinery.interpreter.rete.aggregation.timely.FaithfulSequentialTimelyColumnAggregatorNode; import tools.refinery.interpreter.rete.aggregation.timely.FirstOnlyParallelTimelyColumnAggregatorNode; @@ -72,18 +73,25 @@ class NodeFactory { return parentNode.constructIndex(toMask(recipe.getMask()), traces); // already traced } else if (recipe instanceof AggregatorIndexerRecipe) { - int indexOfAggregateResult = recipe.getParent().getArity(); - int resultPosition = recipe.getMask().getSourceIndices().lastIndexOf(indexOfAggregateResult); - - IAggregatorNode aggregatorNode = (IAggregatorNode) parentNode; - final Indexer result = (resultPosition == -1) ? aggregatorNode.getAggregatorOuterIndexer() - : aggregatorNode.getAggregatorOuterIdentityIndexer(resultPosition); - - for (TraceInfo traceInfo : traces) - result.assignTraceInfo(traceInfo); - return result; - } else - throw new IllegalArgumentException("Unkown Indexer recipe: " + recipe); + int indexOfAggregateResult = recipe.getParent().getArity(); + int resultPosition = recipe.getMask().getSourceIndices().lastIndexOf(indexOfAggregateResult); + + IAggregatorNode aggregatorNode = (IAggregatorNode) parentNode; + final Indexer result = (resultPosition == -1) ? aggregatorNode.getAggregatorOuterIndexer() + : aggregatorNode.getAggregatorOuterIdentityIndexer(resultPosition); + + for (TraceInfo traceInfo : traces) + result.assignTraceInfo(traceInfo); + return result; + } else if (recipe instanceof OuterJoinIndexerRecipe) { + var leftJoinNode = (LeftJoinNode) parentNode; + var result = leftJoinNode.getOuterIndexer(); + for (TraceInfo traceInfo : traces) + result.assignTraceInfo(traceInfo); + return result; + } else { + throw new IllegalArgumentException("Unkown Indexer recipe: " + recipe); + } } /** @@ -134,6 +142,8 @@ class NodeFactory { return instantiateNode(reteContainer, (CountAggregatorRecipe) recipe); if (recipe instanceof SingleColumnAggregatorRecipe) return instantiateNode(reteContainer, (SingleColumnAggregatorRecipe) recipe); + if (recipe instanceof OuterJoinNodeRecipe outerJoinNodeRecipe) + return instantiateNode(reteContainer, outerJoinNodeRecipe); if (recipe instanceof DiscriminatorDispatcherRecipe) return instantiateNode(reteContainer, (DiscriminatorDispatcherRecipe) recipe); if (recipe instanceof DiscriminatorBucketRecipe) @@ -246,6 +256,10 @@ class NodeFactory { } } + private Supplier instantiateNode(ReteContainer reteContainer, OuterJoinNodeRecipe recipe) { + return new LeftJoinNode(reteContainer, recipe.getDefaultValue()); + } + private Supplier instantiateNode(ReteContainer reteContainer, TransitiveClosureRecipe recipe) { return new TransitiveClosureNode(reteContainer); } diff --git a/subprojects/interpreter/src/main/java/tools/refinery/interpreter/matchers/psystem/basicdeferred/LeftJoinConstraint.java b/subprojects/interpreter/src/main/java/tools/refinery/interpreter/matchers/psystem/basicdeferred/LeftJoinConstraint.java new file mode 100644 index 00000000..1c1a895e --- /dev/null +++ b/subprojects/interpreter/src/main/java/tools/refinery/interpreter/matchers/psystem/basicdeferred/LeftJoinConstraint.java @@ -0,0 +1,82 @@ +/******************************************************************************* + * Copyright (c) 2010-2016, Tamas Szabo, Istvan Rath and Daniel Varro + * Copyright (c) 2024 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.interpreter.matchers.psystem.basicdeferred; + +import tools.refinery.interpreter.matchers.context.IQueryMetaContext; +import tools.refinery.interpreter.matchers.psystem.ITypeInfoProviderConstraint; +import tools.refinery.interpreter.matchers.psystem.PBody; +import tools.refinery.interpreter.matchers.psystem.PVariable; +import tools.refinery.interpreter.matchers.psystem.TypeJudgement; +import tools.refinery.interpreter.matchers.psystem.queries.PQuery; +import tools.refinery.interpreter.matchers.tuple.Tuple; +import tools.refinery.interpreter.matchers.tuple.Tuples; + +import java.util.Collections; +import java.util.Set; + +public class LeftJoinConstraint extends PatternCallBasedDeferred implements ITypeInfoProviderConstraint { + protected PVariable resultVariable; + protected int optionalColumn; + protected Object defaultValue; + + public LeftJoinConstraint(PBody pBody, Tuple actualParametersTuple, PQuery query, PVariable resultVariable, + int optionalColumn, Object defaultValue) { + super(pBody, actualParametersTuple, query, Collections.singleton(resultVariable)); + this.resultVariable = resultVariable; + this.optionalColumn = optionalColumn; + this.defaultValue = defaultValue; + } + + public PVariable getResultVariable() { + return resultVariable; + } + + public int getOptionalColumn() { + return optionalColumn; + } + + public Object getDefaultValue() { + return defaultValue; + } + + @Override + public Set getDeducedVariables() { + return Collections.singleton(resultVariable); + } + + @Override + protected void doDoReplaceVariables(PVariable obsolete, PVariable replacement) { + if (resultVariable.equals(obsolete)) { + resultVariable = replacement; + } + } + + @Override + protected Set getCandidateQuantifiedVariables() { + return actualParametersTuple.getDistinctElements(); + } + + @Override + protected String toStringRest() { + return query.getFullyQualifiedName() + "@" + actualParametersTuple.toString() + "->" + + resultVariable.toString(); + } + + @Override + public Set getImpliedJudgements(IQueryMetaContext context) { + var optionalParameter = getReferredQuery().getParameters().get(optionalColumn); + var unaryType = optionalParameter.getDeclaredUnaryType(); + if (unaryType != null && !context.isEnumerable(unaryType)) { + // The outer join makes the result variable non-enumerable, since the default value might not be present in + // the model. + return Set.of(new TypeJudgement(unaryType, Tuples.staticArityFlatTupleOf(resultVariable))); + } + return Set.of(); + } +} diff --git a/subprojects/interpreter/src/main/java/tools/refinery/interpreter/matchers/psystem/rewriters/PBodyCopier.java b/subprojects/interpreter/src/main/java/tools/refinery/interpreter/matchers/psystem/rewriters/PBodyCopier.java index 99350185..1e580599 100644 --- a/subprojects/interpreter/src/main/java/tools/refinery/interpreter/matchers/psystem/rewriters/PBodyCopier.java +++ b/subprojects/interpreter/src/main/java/tools/refinery/interpreter/matchers/psystem/rewriters/PBodyCopier.java @@ -137,7 +137,9 @@ public class PBodyCopier extends AbstractRewriterTraceSource { } else if (constraint instanceof PatternMatchCounter) { copyPatternMatchCounterConstraint((PatternMatchCounter) constraint); } else if (constraint instanceof AggregatorConstraint) { - copyAggregatorConstraint((AggregatorConstraint) constraint); + copyAggregatorConstraint((AggregatorConstraint) constraint); + } else if (constraint instanceof LeftJoinConstraint leftJoinConstraint) { + copyLeftJoinConstraint((LeftJoinConstraint) constraint); } else if (constraint instanceof ExpressionEvaluation) { copyExpressionEvaluationConstraint((ExpressionEvaluation) constraint); } else { @@ -256,6 +258,15 @@ public class PBodyCopier extends AbstractRewriterTraceSource { constraint.getReferredQuery(), mappedResultVariable, constraint.getAggregatedColumn())); } + protected void copyLeftJoinConstraint(LeftJoinConstraint constraint) { + PVariable[] mappedVariables = extractMappedVariables(constraint); + PVariable mappedResultVariable = variableMapping.get(constraint.getResultVariable()); + Tuple variablesTuple = Tuples.flatTupleOf((Object[]) mappedVariables); + addTrace(constraint, new LeftJoinConstraint(body, variablesTuple, + constraint.getReferredQuery(), mappedResultVariable, constraint.getOptionalColumn(), + constraint.getDefaultValue())); + } + protected void copyExpressionEvaluationConstraint(ExpressionEvaluation expressionEvaluation) { PVariable mappedOutputVariable = variableMapping.get(expressionEvaluation.getOutputVariable()); addTrace(expressionEvaluation, new ExpressionEvaluation(body, diff --git a/subprojects/language-ide/src/main/java/tools/refinery/language/ide/syntaxcoloring/ProblemSemanticHighlightingCalculator.java b/subprojects/language-ide/src/main/java/tools/refinery/language/ide/syntaxcoloring/ProblemSemanticHighlightingCalculator.java index 587f9acb..a8849b7c 100644 --- a/subprojects/language-ide/src/main/java/tools/refinery/language/ide/syntaxcoloring/ProblemSemanticHighlightingCalculator.java +++ b/subprojects/language-ide/src/main/java/tools/refinery/language/ide/syntaxcoloring/ProblemSemanticHighlightingCalculator.java @@ -21,7 +21,6 @@ import tools.refinery.language.model.problem.*; import tools.refinery.language.utils.ProblemDesugarer; import tools.refinery.language.utils.ProblemUtil; -import javax.xml.crypto.Data; import java.util.List; public class ProblemSemanticHighlightingCalculator extends DefaultSemanticHighlightingCalculator { diff --git a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/Dnf2PQuery.java b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/Dnf2PQuery.java index 24205cf4..4d30f998 100644 --- a/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/Dnf2PQuery.java +++ b/subprojects/store-query-interpreter/src/main/java/tools/refinery/store/query/interpreter/internal/pquery/Dnf2PQuery.java @@ -1,17 +1,31 @@ /* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors + * SPDX-FileCopyrightText: 2021-2024 The Refinery Authors * * SPDX-License-Identifier: EPL-2.0 */ package tools.refinery.store.query.interpreter.internal.pquery; +import tools.refinery.interpreter.matchers.backend.IQueryBackendFactory; +import tools.refinery.interpreter.matchers.backend.QueryEvaluationHint; +import tools.refinery.interpreter.matchers.context.IInputKey; +import tools.refinery.interpreter.matchers.psystem.PBody; +import tools.refinery.interpreter.matchers.psystem.PVariable; +import tools.refinery.interpreter.matchers.psystem.aggregations.BoundAggregator; +import tools.refinery.interpreter.matchers.psystem.aggregations.IMultisetAggregationOperator; +import tools.refinery.interpreter.matchers.psystem.annotations.PAnnotation; import tools.refinery.interpreter.matchers.psystem.annotations.ParameterReference; import tools.refinery.interpreter.matchers.psystem.basicdeferred.*; -import tools.refinery.interpreter.matchers.psystem.basicenumerables.*; import tools.refinery.interpreter.matchers.psystem.basicenumerables.Connectivity; +import tools.refinery.interpreter.matchers.psystem.basicenumerables.*; +import tools.refinery.interpreter.matchers.psystem.queries.PParameter; +import tools.refinery.interpreter.matchers.psystem.queries.PParameterDirection; +import tools.refinery.interpreter.matchers.psystem.queries.PQuery; +import tools.refinery.interpreter.matchers.tuple.Tuple; +import tools.refinery.interpreter.matchers.tuple.Tuples; import tools.refinery.store.query.Constraint; import tools.refinery.store.query.dnf.Dnf; import tools.refinery.store.query.dnf.DnfClause; +import tools.refinery.store.query.dnf.FunctionalDependency; import tools.refinery.store.query.dnf.SymbolicParameter; import tools.refinery.store.query.literal.*; import tools.refinery.store.query.term.ConstantTerm; @@ -20,19 +34,6 @@ import tools.refinery.store.query.term.StatelessAggregator; import tools.refinery.store.query.term.Variable; import tools.refinery.store.query.view.AnySymbolView; import tools.refinery.store.util.CycleDetectingMapper; -import tools.refinery.interpreter.matchers.backend.IQueryBackendFactory; -import tools.refinery.interpreter.matchers.backend.QueryEvaluationHint; -import tools.refinery.interpreter.matchers.context.IInputKey; -import tools.refinery.interpreter.matchers.psystem.PBody; -import tools.refinery.interpreter.matchers.psystem.PVariable; -import tools.refinery.interpreter.matchers.psystem.aggregations.BoundAggregator; -import tools.refinery.interpreter.matchers.psystem.aggregations.IMultisetAggregationOperator; -import tools.refinery.interpreter.matchers.psystem.annotations.PAnnotation; -import tools.refinery.interpreter.matchers.psystem.queries.PParameter; -import tools.refinery.interpreter.matchers.psystem.queries.PParameterDirection; -import tools.refinery.interpreter.matchers.psystem.queries.PQuery; -import tools.refinery.interpreter.matchers.tuple.Tuple; -import tools.refinery.interpreter.matchers.tuple.Tuples; import java.util.ArrayList; import java.util.HashMap; @@ -79,15 +80,7 @@ public class Dnf2PQuery { pQuery.setParameters(parameterList); for (var functionalDependency : dnfQuery.getFunctionalDependencies()) { - var functionalDependencyAnnotation = new PAnnotation("FunctionalDependency"); - for (var forEachVariable : functionalDependency.forEach()) { - var reference = new ParameterReference(forEachVariable.getUniqueName()); - functionalDependencyAnnotation.addAttribute("forEach", reference); - } - for (var uniqueVariable : functionalDependency.unique()) { - var reference = new ParameterReference(uniqueVariable.getUniqueName()); - functionalDependencyAnnotation.addAttribute("unique", reference); - } + var functionalDependencyAnnotation = getFunctionalDependencyAnnotation(functionalDependency); pQuery.addAnnotation(functionalDependencyAnnotation); } @@ -108,26 +101,33 @@ public class Dnf2PQuery { return pQuery; } - private void translateLiteral(Literal literal, PBody body) { - if (literal instanceof EquivalenceLiteral equivalenceLiteral) { - translateEquivalenceLiteral(equivalenceLiteral, body); - } else if (literal instanceof CallLiteral callLiteral) { - translateCallLiteral(callLiteral, body); - } else if (literal instanceof ConstantLiteral constantLiteral) { - translateConstantLiteral(constantLiteral, body); - } else if (literal instanceof AssignLiteral assignLiteral) { - translateAssignLiteral(assignLiteral, body); - } else if (literal instanceof CheckLiteral checkLiteral) { - translateCheckLiteral(checkLiteral, body); - } else if (literal instanceof CountLiteral countLiteral) { - translateCountLiteral(countLiteral, body); - } else if (literal instanceof AggregationLiteral aggregationLiteral) { - translateAggregationLiteral(aggregationLiteral, body); - } else if (literal instanceof RepresentativeElectionLiteral representativeElectionLiteral) { - translateRepresentativeElectionLiteral(representativeElectionLiteral, body); - } else { - throw new IllegalArgumentException("Unknown literal: " + literal.toString()); + private static PAnnotation getFunctionalDependencyAnnotation(FunctionalDependency functionalDependency) { + var functionalDependencyAnnotation = new PAnnotation("FunctionalDependency"); + for (var forEachVariable : functionalDependency.forEach()) { + var reference = new ParameterReference(forEachVariable.getUniqueName()); + functionalDependencyAnnotation.addAttribute("forEach", reference); + } + for (var uniqueVariable : functionalDependency.unique()) { + var reference = new ParameterReference(uniqueVariable.getUniqueName()); + functionalDependencyAnnotation.addAttribute("unique", reference); } + return functionalDependencyAnnotation; + } + + private void translateLiteral(Literal literal, PBody body) { + switch (literal) { + case EquivalenceLiteral equivalenceLiteral -> translateEquivalenceLiteral(equivalenceLiteral, body); + case CallLiteral callLiteral -> translateCallLiteral(callLiteral, body); + case ConstantLiteral constantLiteral -> translateConstantLiteral(constantLiteral, body); + case AssignLiteral assignLiteral -> translateAssignLiteral(assignLiteral, body); + case CheckLiteral checkLiteral -> translateCheckLiteral(checkLiteral, body); + case CountLiteral countLiteral -> translateCountLiteral(countLiteral, body); + case AggregationLiteral aggregationLiteral -> translateAggregationLiteral(aggregationLiteral, body); + case LeftJoinLiteral leftJoinLiteral -> translateLeftJoinLiteral(leftJoinLiteral, body); + case RepresentativeElectionLiteral representativeElectionLiteral -> + translateRepresentativeElectionLiteral(representativeElectionLiteral, body); + case null, default -> throw new IllegalArgumentException("Unknown literal: " + literal); + } } private void translateEquivalenceLiteral(EquivalenceLiteral equivalenceLiteral, PBody body) { @@ -244,6 +244,21 @@ public class Dnf2PQuery { aggregatedColumn); } + private void translateLeftJoinLiteral(LeftJoinLiteral leftJoinLiteral, PBody body) { + var wrappedCall = wrapperFactory.maybeWrapConstraint(leftJoinLiteral); + var substitution = translateSubstitution(wrappedCall.remappedArguments(), body); + var placeholderVariable = body.getOrCreateVariableByName( + leftJoinLiteral.getPlaceholderVariable().getUniqueName()); + var optionalColumn = substitution.invertIndex().get(placeholderVariable); + if (optionalColumn == null) { + throw new IllegalStateException("Placeholder variable %s not found in substitution %s" + .formatted(placeholderVariable, substitution)); + } + var resultVariable = body.getOrCreateVariableByName(leftJoinLiteral.getResultVariable().getUniqueName()); + new LeftJoinConstraint(body, substitution, wrappedCall.pattern(), resultVariable, optionalColumn, + leftJoinLiteral.getDefaultValue()); + } + private void translateRepresentativeElectionLiteral(RepresentativeElectionLiteral literal, PBody body) { var substitution = translateSubstitution(literal.getArguments(), body); var pattern = wrapConstraintWithIdentityArguments(literal.getTarget()); diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/FunctionalQueryTest.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/FunctionalQueryTest.java index b6c96676..ca1512d8 100644 --- a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/FunctionalQueryTest.java +++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/FunctionalQueryTest.java @@ -553,7 +553,6 @@ class FunctionalQueryTest { friendInterpretation.put(Tuple.of(1, 0), TruthValue.TRUE); friendInterpretation.put(Tuple.of(1, 2), TruthValue.TRUE); - queryEngine.flushChanges(); queryEngine.flushChanges(); assertNullableResults(Map.of( Tuple.of(0), Optional.of(25), diff --git a/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/LeftJoinTest.java b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/LeftJoinTest.java new file mode 100644 index 00000000..4c849e9d --- /dev/null +++ b/subprojects/store-query-interpreter/src/test/java/tools/refinery/store/query/interpreter/LeftJoinTest.java @@ -0,0 +1,129 @@ +/* + * SPDX-FileCopyrightText: 2024 The Refinery Authors + * + * SPDX-License-Identifier: EPL-2.0 + */ +package tools.refinery.store.query.interpreter; + +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.term.int_.IntTerms; +import tools.refinery.store.query.view.AnySymbolView; +import tools.refinery.store.query.view.FunctionView; +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 java.util.Optional; + +import static tools.refinery.store.query.interpreter.tests.QueryAssertions.assertNullableResults; +import static tools.refinery.store.query.interpreter.tests.QueryAssertions.assertResults; + +class LeftJoinTest { + private static final Symbol person = Symbol.of("Person", 1); + private static final Symbol age = Symbol.of("age", 1, Integer.class); + private static final AnySymbolView personView = new KeyOnlyView<>(person); + private static final FunctionView ageView = new FunctionView<>(age); + + @Test + void unarySymbolTest() { + var query = Query.of("Query", Integer.class, (builder, p1, output) -> builder + .clause( + personView.call(p1), + output.assign(ageView.leftJoin(18, p1)) + )); + + var store = ModelStore.builder() + .symbols(person, age) + .with(QueryInterpreterAdapter.builder() + .queries(query)) + .build(); + + var model = store.createEmptyModel(); + var personInterpretation = model.getInterpretation(person); + var ageInterpretation = model.getInterpretation(age); + var queryEngine = model.getAdapter(ModelQueryAdapter.class); + var queryResultSet = queryEngine.getResultSet(query); + + personInterpretation.put(Tuple.of(0), true); + personInterpretation.put(Tuple.of(1), true); + personInterpretation.put(Tuple.of(2), true); + + ageInterpretation.put(Tuple.of(2), 24); + + queryEngine.flushChanges(); + assertNullableResults(Map.of( + Tuple.of(0), Optional.of(18), + Tuple.of(1), Optional.of(18), + Tuple.of(2), Optional.of(24), + Tuple.of(3), Optional.empty() + ), queryResultSet); + + personInterpretation.put(Tuple.of(0), false); + + ageInterpretation.put(Tuple.of(1), 20); + ageInterpretation.put(Tuple.of(2), null); + + queryEngine.flushChanges(); + assertNullableResults(Map.of( + Tuple.of(0), Optional.empty(), + Tuple.of(1), Optional.of(20), + Tuple.of(2), Optional.of(18), + Tuple.of(3), Optional.empty() + ), queryResultSet); + } + + @Test + void unarySymbolWithAssignmentTest() { + // Tests an edge case where the outer joined variable is already bound in the query plan. + var query = Query.of("Query", (builder, p1) -> builder + .clause(Integer.class, v1 -> List.of( + personView.call(p1), + v1.assign(IntTerms.constant(18)), + v1.assign(ageView.leftJoin(18, p1)) + ))); + + var store = ModelStore.builder() + .symbols(person, age) + .with(QueryInterpreterAdapter.builder() + .queries(query)) + .build(); + + var model = store.createEmptyModel(); + var personInterpretation = model.getInterpretation(person); + var ageInterpretation = model.getInterpretation(age); + var queryEngine = model.getAdapter(ModelQueryAdapter.class); + var queryResultSet = queryEngine.getResultSet(query); + + personInterpretation.put(Tuple.of(0), true); + personInterpretation.put(Tuple.of(1), true); + personInterpretation.put(Tuple.of(2), true); + + ageInterpretation.put(Tuple.of(2), 24); + + queryEngine.flushChanges(); + assertResults(Map.of( + Tuple.of(0), true, + Tuple.of(1), true, + Tuple.of(2), false, + Tuple.of(3), false + ), queryResultSet); + + personInterpretation.put(Tuple.of(0), false); + + ageInterpretation.put(Tuple.of(1), 20); + ageInterpretation.put(Tuple.of(2), null); + + queryEngine.flushChanges(); + assertResults(Map.of( + Tuple.of(0), false, + Tuple.of(1), false, + Tuple.of(2), true, + Tuple.of(3), false + ), queryResultSet); + } +} diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/Constraint.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/Constraint.java index 916fb35c..375c582a 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/Constraint.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/Constraint.java @@ -1,5 +1,5 @@ /* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors + * SPDX-FileCopyrightText: 2021-2024 The Refinery Authors * * SPDX-License-Identifier: EPL-2.0 */ @@ -69,4 +69,14 @@ public interface Constraint { Variable... arguments) { return aggregateBy(inputVariable, aggregator, List.of(arguments)); } + + default AssignedValue leftJoinBy(DataVariable placeholderVariable, T defaultValue, + List arguments) { + return targetVariable -> new LeftJoinLiteral<>(targetVariable, placeholderVariable, defaultValue, this, + arguments); + } + + default AssignedValue leftJoinBy(DataVariable inputVariable, T defaultValue, Variable... arguments) { + return leftJoinBy(inputVariable, defaultValue, List.of(arguments)); + } } diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/ClausePostProcessor.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/ClausePostProcessor.java index 8800a155..7cd05364 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/ClausePostProcessor.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/ClausePostProcessor.java @@ -1,5 +1,5 @@ /* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors + * SPDX-FileCopyrightText: 2021-2024 The Refinery Authors * * SPDX-License-Identifier: EPL-2.0 */ @@ -112,7 +112,7 @@ class ClausePostProcessor { .formatted(variable, representative)); } return equivalencePartition.computeIfAbsent(variable, key -> { - var set = new HashSet(1); + var set = HashSet.newHashSet(1); set.add(key); return set; }); @@ -193,7 +193,7 @@ class ClausePostProcessor { } private void topologicallySortLiterals() { - topologicallySortedLiterals = new LinkedHashSet<>(substitutedLiterals.size()); + topologicallySortedLiterals = LinkedHashSet.newLinkedHashSet(substitutedLiterals.size()); variableToLiteralInputMap = new HashMap<>(); literalsWithAllInputsBound = new PriorityQueue<>(); int size = substitutedLiterals.size(); diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfPostProcessor.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfPostProcessor.java index 50236642..01344b59 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfPostProcessor.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/DnfPostProcessor.java @@ -1,5 +1,5 @@ /* - * SPDX-FileCopyrightText: 2023 The Refinery Authors + * SPDX-FileCopyrightText: 2023-2024 The Refinery Authors * * SPDX-License-Identifier: EPL-2.0 */ @@ -26,7 +26,7 @@ class DnfPostProcessor { public List postProcessClauses() { var parameterInfoMap = getParameterInfoMap(); - var postProcessedClauses = new LinkedHashSet(clauses.size()); + var postProcessedClauses = LinkedHashSet.newLinkedHashSet(clauses.size()); int index = 0; for (var literals : clauses) { var postProcessor = new ClausePostProcessor(parameterInfoMap, literals); diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalQuery.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalQuery.java index 225f6844..b0a03c7d 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalQuery.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/dnf/FunctionalQuery.java @@ -1,5 +1,5 @@ /* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors + * SPDX-FileCopyrightText: 2021-2024 The Refinery Authors * * SPDX-License-Identifier: EPL-2.0 */ @@ -94,6 +94,22 @@ public final class FunctionalQuery extends Query { return aggregate(aggregator, List.of(arguments)); } + public AssignedValue leftJoin(T defaultValue, List arguments) { + return targetVariable -> { + var placeholderVariable = Variable.of(type); + var argumentsWithPlaceholder = new ArrayList(arguments.size() + 1); + argumentsWithPlaceholder.addAll(arguments); + argumentsWithPlaceholder.add(placeholderVariable); + return getDnf() + .leftJoinBy(placeholderVariable, defaultValue, argumentsWithPlaceholder) + .toLiteral(targetVariable); + }; + } + + public AssignedValue leftJoin(T defaultValue, NodeVariable... arguments) { + return leftJoin(defaultValue, List.of(arguments)); + } + @Override public boolean equals(Object o) { if (this == o) return true; diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AggregationLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AggregationLiteral.java index e3acfacc..b6861de0 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AggregationLiteral.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/AggregationLiteral.java @@ -1,5 +1,5 @@ /* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors + * SPDX-FileCopyrightText: 2021-2024 The Refinery Authors * * SPDX-License-Identifier: EPL-2.0 */ @@ -129,7 +129,12 @@ public class AggregationLiteral extends AbstractCallLiteral { } builder.append(argument); while (argumentIterator.hasNext()) { - builder.append(", ").append(argumentIterator.next()); + builder.append(", "); + argument = argumentIterator.next(); + if (inputVariable.equals(argument)) { + builder.append("@Aggregate(\"").append(aggregator).append("\") "); + } + builder.append(argument); } } builder.append(")"); diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/LeftJoinLiteral.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/LeftJoinLiteral.java new file mode 100644 index 00000000..bdddf120 --- /dev/null +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/literal/LeftJoinLiteral.java @@ -0,0 +1,140 @@ +/* + * SPDX-FileCopyrightText: 2024 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.InvalidQueryException; +import tools.refinery.store.query.equality.LiteralEqualityHelper; +import tools.refinery.store.query.equality.LiteralHashCodeHelper; +import tools.refinery.store.query.substitution.Substitution; +import tools.refinery.store.query.term.ConstantTerm; +import tools.refinery.store.query.term.DataVariable; +import tools.refinery.store.query.term.ParameterDirection; +import tools.refinery.store.query.term.Variable; + +import java.util.*; + +// {@link Object#equals(Object)} is implemented by {@link AbstractLiteral}. +@SuppressWarnings("squid:S2160") +public class LeftJoinLiteral extends AbstractCallLiteral { + private final DataVariable resultVariable; + private final DataVariable placeholderVariable; + private final T defaultValue; + + public LeftJoinLiteral(DataVariable resultVariable, DataVariable placeholderVariable, + T defaultValue, Constraint target, List arguments) { + super(target, arguments); + this.resultVariable = resultVariable; + this.placeholderVariable = placeholderVariable; + this.defaultValue = defaultValue; + if (defaultValue == null) { + throw new InvalidQueryException("Default value must not be null"); + } + if (!resultVariable.getType().isInstance(defaultValue)) { + throw new InvalidQueryException("Default value %s must be assignable to result variable %s type %s" + .formatted(defaultValue, resultVariable, resultVariable.getType().getName())); + } + if (!getArgumentsOfDirection(ParameterDirection.OUT).contains(placeholderVariable)) { + throw new InvalidQueryException( + "Placeholder variable %s must be bound with direction %s in the argument list" + .formatted(resultVariable, ParameterDirection.OUT)); + } + if (arguments.contains(resultVariable)) { + throw new InvalidQueryException("Result variable must not appear in the argument list"); + } + } + + public DataVariable getResultVariable() { + return resultVariable; + } + + public DataVariable getPlaceholderVariable() { + return placeholderVariable; + } + + public T getDefaultValue() { + return defaultValue; + } + + @Override + public Set getOutputVariables() { + return Set.of(resultVariable); + } + + @Override + public Set getInputVariables(Set positiveVariablesInClause) { + var inputVariables = new LinkedHashSet<>(getArguments()); + inputVariables.remove(placeholderVariable); + return Collections.unmodifiableSet(inputVariables); + } + + @Override + public Set getPrivateVariables(Set positiveVariablesInClause) { + return Set.of(placeholderVariable); + } + + @Override + public Literal reduce() { + var reduction = getTarget().getReduction(); + return switch (reduction) { + case ALWAYS_FALSE -> resultVariable.assign(new ConstantTerm<>(resultVariable.getType(), defaultValue)); + case ALWAYS_TRUE -> throw new InvalidQueryException("Trying to left join an infinite set"); + case NOT_REDUCIBLE -> this; + }; + } + + @Override + protected Literal doSubstitute(Substitution substitution, List substitutedArguments) { + return new LeftJoinLiteral<>(substitution.getTypeSafeSubstitute(resultVariable), + substitution.getTypeSafeSubstitute(placeholderVariable), defaultValue, getTarget(), + substitutedArguments); + } + + @Override + public AbstractCallLiteral withArguments(Constraint newTarget, List newArguments) { + return new LeftJoinLiteral<>(resultVariable, placeholderVariable, defaultValue, newTarget, newArguments); + } + + @Override + public boolean equalsWithSubstitution(LiteralEqualityHelper helper, Literal other) { + if (!super.equalsWithSubstitution(helper, other)) { + return false; + } + var otherLeftJoinLiteral = (LeftJoinLiteral) other; + return helper.variableEqual(resultVariable, otherLeftJoinLiteral.resultVariable) && + helper.variableEqual(placeholderVariable, otherLeftJoinLiteral.placeholderVariable) && + Objects.equals(defaultValue, otherLeftJoinLiteral.defaultValue); + } + + @Override + public int hashCodeWithSubstitution(LiteralHashCodeHelper helper) { + return Objects.hash(super.hashCodeWithSubstitution(helper), helper.getVariableHashCode(resultVariable), + helper.getVariableHashCode(placeholderVariable), defaultValue); + } + + @Override + public String toString() { + var builder = new StringBuilder(); + var argumentIterator = getArguments().iterator(); + if (argumentIterator.hasNext()) { + appendArgument(builder, argumentIterator.next()); + while (argumentIterator.hasNext()) { + builder.append(", "); + appendArgument(builder, argumentIterator.next()); + } + } + builder.append(")"); + return builder.toString(); + } + + private void appendArgument(StringBuilder builder, Variable argument) { + if (placeholderVariable.equals(argument)) { + builder.append("@Default(").append(defaultValue).append(") "); + argument = resultVariable; + } + builder.append(argument); + } +} diff --git a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FunctionView.java b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FunctionView.java index 74a5be07..3dfb6777 100644 --- a/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FunctionView.java +++ b/subprojects/store-query/src/main/java/tools/refinery/store/query/view/FunctionView.java @@ -1,5 +1,5 @@ /* - * SPDX-FileCopyrightText: 2021-2023 The Refinery Authors + * SPDX-FileCopyrightText: 2021-2024 The Refinery Authors * * SPDX-License-Identifier: EPL-2.0 */ @@ -33,4 +33,18 @@ public final class FunctionView extends AbstractFunctionView { public AssignedValue aggregate(Aggregator aggregator, NodeVariable... arguments) { return aggregate(aggregator, List.of(arguments)); } + + public AssignedValue leftJoin(T defaultValue, List arguments) { + return targetVariable -> { + var placeholderVariable = Variable.of(getSymbol().valueType()); + var argumentsWithPlaceholder = new ArrayList(arguments.size() + 1); + argumentsWithPlaceholder.addAll(arguments); + argumentsWithPlaceholder.add(placeholderVariable); + return leftJoinBy(placeholderVariable, defaultValue, argumentsWithPlaceholder).toLiteral(targetVariable); + }; + } + + public AssignedValue leftJoin(T defaultValue, NodeVariable... arguments) { + return leftJoin(defaultValue, List.of(arguments)); + } } -- cgit v1.2.3-54-g00ecf