diff options
author | Kristóf Marussy <marussy@mit.bme.hu> | 2023-09-14 19:29:36 +0200 |
---|---|---|
committer | GitHub <noreply@github.com> | 2023-09-14 19:29:36 +0200 |
commit | 98ed3b6db5f4e51961a161050cc31c66015116e8 (patch) | |
tree | 8bfd6d9bc8d6ed23b9eb0f889dd40b6c24fe8f92 /subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/construction/quasitree/QuasiTreeLayout.java | |
parent | Merge pull request #38 from nagilooh/design-space-exploration (diff) | |
parent | Merge remote-tracking branch 'upstream/main' into partial-interpretation (diff) | |
download | refinery-98ed3b6db5f4e51961a161050cc31c66015116e8.tar.gz refinery-98ed3b6db5f4e51961a161050cc31c66015116e8.tar.zst refinery-98ed3b6db5f4e51961a161050cc31c66015116e8.zip |
Merge pull request #39 from kris7t/partial-interpretation
Implement partial interpretation based model generation
Diffstat (limited to 'subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/construction/quasitree/QuasiTreeLayout.java')
-rw-r--r-- | subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/construction/quasitree/QuasiTreeLayout.java | 205 |
1 files changed, 205 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/construction/quasitree/QuasiTreeLayout.java b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/construction/quasitree/QuasiTreeLayout.java new file mode 100644 index 00000000..9b814376 --- /dev/null +++ b/subprojects/viatra-runtime-rete/src/main/java/tools/refinery/viatra/runtime/rete/construction/quasitree/QuasiTreeLayout.java | |||
@@ -0,0 +1,205 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2004-2010 Gabor Bergmann and Daniel Varro | ||
3 | * This program and the accompanying materials are made available under the | ||
4 | * terms of the Eclipse Public License v. 2.0 which is available at | ||
5 | * http://www.eclipse.org/legal/epl-v20.html. | ||
6 | * | ||
7 | * SPDX-License-Identifier: EPL-2.0 | ||
8 | *******************************************************************************/ | ||
9 | |||
10 | package tools.refinery.viatra.runtime.rete.construction.quasitree; | ||
11 | |||
12 | import java.util.ArrayList; | ||
13 | import java.util.Collections; | ||
14 | import java.util.LinkedHashSet; | ||
15 | import java.util.List; | ||
16 | import java.util.Set; | ||
17 | |||
18 | import org.apache.log4j.Logger; | ||
19 | import tools.refinery.viatra.runtime.matchers.ViatraQueryRuntimeException; | ||
20 | import tools.refinery.viatra.runtime.matchers.backend.IQueryBackendHintProvider; | ||
21 | import tools.refinery.viatra.runtime.matchers.backend.QueryEvaluationHint; | ||
22 | import tools.refinery.viatra.runtime.matchers.context.IQueryBackendContext; | ||
23 | import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext; | ||
24 | import tools.refinery.viatra.runtime.matchers.planning.IQueryPlannerStrategy; | ||
25 | import tools.refinery.viatra.runtime.matchers.planning.SubPlan; | ||
26 | import tools.refinery.viatra.runtime.matchers.planning.SubPlanFactory; | ||
27 | import tools.refinery.viatra.runtime.matchers.planning.helpers.BuildHelper; | ||
28 | import tools.refinery.viatra.runtime.matchers.planning.operations.PApply; | ||
29 | import tools.refinery.viatra.runtime.matchers.planning.operations.PEnumerate; | ||
30 | import tools.refinery.viatra.runtime.matchers.planning.operations.PProject; | ||
31 | import tools.refinery.viatra.runtime.matchers.planning.operations.PStart; | ||
32 | import tools.refinery.viatra.runtime.matchers.psystem.DeferredPConstraint; | ||
33 | import tools.refinery.viatra.runtime.matchers.psystem.EnumerablePConstraint; | ||
34 | import tools.refinery.viatra.runtime.matchers.psystem.PBody; | ||
35 | import tools.refinery.viatra.runtime.matchers.psystem.analysis.QueryAnalyzer; | ||
36 | import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.ConstantValue; | ||
37 | import tools.refinery.viatra.runtime.matchers.psystem.queries.PQuery; | ||
38 | import tools.refinery.viatra.runtime.rete.construction.RetePatternBuildException; | ||
39 | import tools.refinery.viatra.runtime.rete.util.ReteHintOptions; | ||
40 | |||
41 | /** | ||
42 | * Layout ideas: see https://bugs.eclipse.org/bugs/show_bug.cgi?id=398763 | ||
43 | * | ||
44 | * @author Gabor Bergmann | ||
45 | * | ||
46 | */ | ||
47 | public class QuasiTreeLayout implements IQueryPlannerStrategy { | ||
48 | |||
49 | private IQueryBackendHintProvider hintProvider; | ||
50 | private IQueryBackendContext backendContext; | ||
51 | private QueryAnalyzer queryAnalyzer; | ||
52 | |||
53 | public QuasiTreeLayout(IQueryBackendContext backendContext) { | ||
54 | this(backendContext, backendContext.getHintProvider()); | ||
55 | } | ||
56 | |||
57 | public QuasiTreeLayout(IQueryBackendContext backendContext, IQueryBackendHintProvider hintProvider) { | ||
58 | this.backendContext = backendContext; | ||
59 | this.hintProvider = hintProvider; | ||
60 | queryAnalyzer = backendContext.getQueryAnalyzer(); | ||
61 | } | ||
62 | |||
63 | @Override | ||
64 | public SubPlan plan(PBody pSystem, Logger logger, IQueryMetaContext context) { | ||
65 | return new Scaffold(pSystem, logger, context).run(); | ||
66 | } | ||
67 | |||
68 | public class Scaffold { | ||
69 | PBody pSystem; | ||
70 | PQuery query; | ||
71 | IQueryMetaContext context; | ||
72 | private QueryEvaluationHint hints; | ||
73 | //IOperationCompiler compiler; | ||
74 | //SubPlanProcessor planProcessor = new SubPlanProcessor(); | ||
75 | SubPlanFactory planFactory; | ||
76 | |||
77 | Set<DeferredPConstraint> deferredConstraints = null; | ||
78 | Set<EnumerablePConstraint> enumerableConstraints = null; | ||
79 | Set<ConstantValue> constantConstraints = null; | ||
80 | Set<SubPlan> forefront = new LinkedHashSet<SubPlan>(); | ||
81 | Logger logger; | ||
82 | |||
83 | Scaffold(PBody pSystem, Logger logger, /*IOperationCompiler compiler,*/ IQueryMetaContext context) { | ||
84 | this.pSystem = pSystem; | ||
85 | this.logger = logger; | ||
86 | this.context = context; | ||
87 | this.planFactory = new SubPlanFactory(pSystem); | ||
88 | query = pSystem.getPattern(); | ||
89 | //this.compiler = compiler; | ||
90 | //planProcessor.setCompiler(compiler); | ||
91 | |||
92 | hints = hintProvider.getQueryEvaluationHint(query); | ||
93 | } | ||
94 | |||
95 | /** | ||
96 | * @throws ViatraQueryRuntimeException | ||
97 | */ | ||
98 | public SubPlan run() { | ||
99 | try { | ||
100 | logger.debug(String.format( | ||
101 | "%s: patternbody build started for %s", | ||
102 | getClass().getSimpleName(), | ||
103 | query.getFullyQualifiedName())); | ||
104 | |||
105 | // PROCESS CONSTRAINTS | ||
106 | deferredConstraints = pSystem.getConstraintsOfType(DeferredPConstraint.class); | ||
107 | enumerableConstraints = pSystem.getConstraintsOfType(EnumerablePConstraint.class); | ||
108 | constantConstraints = pSystem.getConstraintsOfType(ConstantValue.class); | ||
109 | |||
110 | for (EnumerablePConstraint enumerable : enumerableConstraints) { | ||
111 | SubPlan plan = planFactory.createSubPlan(new PEnumerate(enumerable)); | ||
112 | admitSubPlan(plan); | ||
113 | } | ||
114 | if (enumerableConstraints.isEmpty()) { // EXTREME CASE | ||
115 | SubPlan plan = planFactory.createSubPlan(new PStart()); | ||
116 | admitSubPlan(plan); | ||
117 | } | ||
118 | |||
119 | // JOIN FOREFRONT PLANS WHILE POSSIBLE | ||
120 | while (forefront.size() > 1) { | ||
121 | // TODO QUASI-TREE TRIVIAL JOINS? | ||
122 | |||
123 | List<JoinCandidate> candidates = generateJoinCandidates(); | ||
124 | JoinOrderingHeuristics ordering = new JoinOrderingHeuristics(); | ||
125 | JoinCandidate selectedJoin = Collections.min(candidates, ordering); | ||
126 | doJoin(selectedJoin); | ||
127 | } | ||
128 | assert (forefront.size() == 1); | ||
129 | |||
130 | // PROJECT TO PARAMETERS | ||
131 | SubPlan preFinalPlan = forefront.iterator().next(); | ||
132 | SubPlan finalPlan = planFactory.createSubPlan(new PProject(pSystem.getSymbolicParameterVariables()), preFinalPlan); | ||
133 | |||
134 | // FINAL CHECK, whether all exported variables are present + all constraint satisfied | ||
135 | BuildHelper.finalCheck(pSystem, finalPlan, context); | ||
136 | // TODO integrate the check above in SubPlan / POperation | ||
137 | |||
138 | logger.debug(String.format( | ||
139 | "%s: patternbody query plan concluded for %s as: %s", | ||
140 | getClass().getSimpleName(), | ||
141 | query.getFullyQualifiedName(), | ||
142 | finalPlan.toLongString())); | ||
143 | return finalPlan; | ||
144 | } catch (RetePatternBuildException ex) { | ||
145 | ex.setPatternDescription(query); | ||
146 | throw ex; | ||
147 | } | ||
148 | } | ||
149 | |||
150 | public List<JoinCandidate> generateJoinCandidates() { | ||
151 | List<JoinCandidate> candidates = new ArrayList<JoinCandidate>(); | ||
152 | int bIndex = 0; | ||
153 | for (SubPlan b : forefront) { | ||
154 | int aIndex = 0; | ||
155 | for (SubPlan a : forefront) { | ||
156 | if (aIndex++ >= bIndex) | ||
157 | break; | ||
158 | candidates.add(new JoinCandidate(a, b, queryAnalyzer)); | ||
159 | } | ||
160 | bIndex++; | ||
161 | } | ||
162 | return candidates; | ||
163 | } | ||
164 | |||
165 | private void admitSubPlan(SubPlan plan) { | ||
166 | // are there any unapplied constant filters that we can apply here? | ||
167 | if (ReteHintOptions.prioritizeConstantFiltering.getValueOrDefault(hints)) { | ||
168 | for (ConstantValue constantConstraint : constantConstraints) { | ||
169 | if (!plan.getAllEnforcedConstraints().contains(constantConstraint) && | ||
170 | plan.getVisibleVariables().containsAll(constantConstraint.getAffectedVariables())) { | ||
171 | plan = planFactory.createSubPlan(new PApply(constantConstraint), plan); | ||
172 | } | ||
173 | } | ||
174 | } | ||
175 | // are there any variables that will not be needed anymore and are worth trimming? | ||
176 | // (check only if there are unenforced enumerables, so that there are still upcoming joins) | ||
177 | // if (Options.planTrimOption != Options.PlanTrimOption.OFF && | ||
178 | // !plan.getAllEnforcedConstraints().containsAll(enumerableConstraints)) { | ||
179 | if (true) { | ||
180 | final SubPlan trimmed = BuildHelper.trimUnneccessaryVariables( | ||
181 | planFactory, plan, true, queryAnalyzer); | ||
182 | plan = trimmed; | ||
183 | } | ||
184 | // are there any checkable constraints? | ||
185 | for (DeferredPConstraint deferred : deferredConstraints) { | ||
186 | if (!plan.getAllEnforcedConstraints().contains(deferred)) { | ||
187 | if (deferred.isReadyAt(plan, context)) { | ||
188 | admitSubPlan(planFactory.createSubPlan(new PApply(deferred), plan)); | ||
189 | return; | ||
190 | } | ||
191 | } | ||
192 | } | ||
193 | // if no checkable constraints and no unused variables | ||
194 | forefront.add(plan); | ||
195 | } | ||
196 | |||
197 | private void doJoin(JoinCandidate selectedJoin) { | ||
198 | forefront.remove(selectedJoin.getPrimary()); | ||
199 | forefront.remove(selectedJoin.getSecondary()); | ||
200 | admitSubPlan(selectedJoin.getJoinedPlan(planFactory)); | ||
201 | } | ||
202 | |||
203 | } | ||
204 | |||
205 | } | ||