diff options
Diffstat (limited to 'subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintInfoInferrer.java')
-rw-r--r-- | subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintInfoInferrer.java | 278 |
1 files changed, 278 insertions, 0 deletions
diff --git a/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintInfoInferrer.java b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintInfoInferrer.java new file mode 100644 index 00000000..eeac07ce --- /dev/null +++ b/subprojects/viatra-runtime-localsearch/src/main/java/tools/refinery/viatra/runtime/localsearch/planner/PConstraintInfoInferrer.java | |||
@@ -0,0 +1,278 @@ | |||
1 | /******************************************************************************* | ||
2 | * Copyright (c) 2010-2016, Grill Balázs, IncQuery Labs Ltd. | ||
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 | package tools.refinery.viatra.runtime.localsearch.planner; | ||
10 | |||
11 | import tools.refinery.viatra.runtime.localsearch.planner.cost.IConstraintEvaluationContext; | ||
12 | import tools.refinery.viatra.runtime.matchers.backend.ResultProviderRequestor; | ||
13 | import tools.refinery.viatra.runtime.matchers.context.IInputKey; | ||
14 | import tools.refinery.viatra.runtime.matchers.context.IQueryBackendContext; | ||
15 | import tools.refinery.viatra.runtime.matchers.psystem.PConstraint; | ||
16 | import tools.refinery.viatra.runtime.matchers.psystem.PVariable; | ||
17 | import tools.refinery.viatra.runtime.matchers.psystem.basicdeferred.*; | ||
18 | import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.AbstractTransitiveClosure; | ||
19 | import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.ConstantValue; | ||
20 | import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.PositivePatternCall; | ||
21 | import tools.refinery.viatra.runtime.matchers.psystem.basicenumerables.TypeConstraint; | ||
22 | import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameter; | ||
23 | import tools.refinery.viatra.runtime.matchers.psystem.queries.PParameterDirection; | ||
24 | import tools.refinery.viatra.runtime.matchers.tuple.Tuple; | ||
25 | import tools.refinery.viatra.runtime.matchers.util.Sets; | ||
26 | |||
27 | import java.util.*; | ||
28 | import java.util.function.Function; | ||
29 | import java.util.function.Predicate; | ||
30 | import java.util.stream.Collectors; | ||
31 | import java.util.stream.Stream; | ||
32 | |||
33 | |||
34 | /** | ||
35 | * @author Grill Balázs | ||
36 | * @noreference This class is not intended to be referenced by clients. | ||
37 | */ | ||
38 | class PConstraintInfoInferrer { | ||
39 | |||
40 | private static final Predicate<PVariable> SINGLE_USE_VARIABLE = input -> input != null && input.getReferringConstraints().size() == 1; | ||
41 | |||
42 | private final boolean useIndex; | ||
43 | private final Function<IConstraintEvaluationContext, Double> costFunction; | ||
44 | private final IQueryBackendContext context; | ||
45 | private final ResultProviderRequestor resultRequestor; | ||
46 | |||
47 | |||
48 | public PConstraintInfoInferrer(boolean useIndex, | ||
49 | IQueryBackendContext backendContext, | ||
50 | ResultProviderRequestor resultRequestor, | ||
51 | Function<IConstraintEvaluationContext, Double> costFunction) { | ||
52 | this.useIndex = useIndex; | ||
53 | this.context = backendContext; | ||
54 | this.resultRequestor = resultRequestor; | ||
55 | this.costFunction = costFunction; | ||
56 | } | ||
57 | |||
58 | |||
59 | /** | ||
60 | * Create all possible application condition for all constraint | ||
61 | * | ||
62 | * @param constraintSet the set of constraints | ||
63 | * @return a collection of the wrapper PConstraintInfo objects with all the allowed application conditions | ||
64 | */ | ||
65 | public List<PConstraintInfo> createPConstraintInfos(Set<PConstraint> constraintSet) { | ||
66 | List<PConstraintInfo> constraintInfos = new ArrayList<>(); | ||
67 | |||
68 | for (PConstraint pConstraint : constraintSet) { | ||
69 | createPConstraintInfoDispatch(constraintInfos, pConstraint); | ||
70 | } | ||
71 | return constraintInfos; | ||
72 | } | ||
73 | |||
74 | private void createPConstraintInfoDispatch(List<PConstraintInfo> resultList, PConstraint pConstraint){ | ||
75 | if(pConstraint instanceof ExportedParameter){ | ||
76 | createConstraintInfoExportedParameter(resultList, (ExportedParameter) pConstraint); | ||
77 | } else if(pConstraint instanceof TypeConstraint){ | ||
78 | createConstraintInfoTypeConstraint(resultList, (TypeConstraint)pConstraint); | ||
79 | } else if(pConstraint instanceof TypeFilterConstraint){ | ||
80 | createConstraintInfoTypeFilterConstraint(resultList, (TypeFilterConstraint)pConstraint); | ||
81 | } else if(pConstraint instanceof ConstantValue){ | ||
82 | createConstraintInfoConstantValue(resultList, (ConstantValue)pConstraint); | ||
83 | } else if (pConstraint instanceof Inequality){ | ||
84 | createConstraintInfoInequality(resultList, (Inequality) pConstraint); | ||
85 | } else if (pConstraint instanceof ExpressionEvaluation){ | ||
86 | createConstraintInfoExpressionEvaluation(resultList, (ExpressionEvaluation)pConstraint); | ||
87 | } else if (pConstraint instanceof AggregatorConstraint){ | ||
88 | createConstraintInfoAggregatorConstraint(resultList, pConstraint, ((AggregatorConstraint) pConstraint).getResultVariable()); | ||
89 | } else if (pConstraint instanceof PatternMatchCounter){ | ||
90 | createConstraintInfoAggregatorConstraint(resultList, pConstraint, ((PatternMatchCounter) pConstraint).getResultVariable()); | ||
91 | } else if (pConstraint instanceof PositivePatternCall){ | ||
92 | createConstraintInfoPositivePatternCall(resultList, (PositivePatternCall) pConstraint); | ||
93 | } else if (pConstraint instanceof AbstractTransitiveClosure) { | ||
94 | createConstraintInfoBinaryTransitiveClosure(resultList, (AbstractTransitiveClosure) pConstraint); | ||
95 | } else{ | ||
96 | createConstraintInfoGeneric(resultList, pConstraint); | ||
97 | } | ||
98 | } | ||
99 | |||
100 | private void createConstraintInfoConstantValue(List<PConstraintInfo> resultList, | ||
101 | ConstantValue pConstraint) { | ||
102 | // A ConstantValue constraint has a single variable, which is allowed to be unbound | ||
103 | // (extending through ConstantValue is considered a cheap operation) | ||
104 | Set<PVariable> affectedVariables = pConstraint.getAffectedVariables(); | ||
105 | Set<? extends Set<PVariable>> bindings = Sets.powerSet(affectedVariables); | ||
106 | doCreateConstraintInfos(resultList, pConstraint, affectedVariables, bindings); | ||
107 | } | ||
108 | |||
109 | |||
110 | private void createConstraintInfoPositivePatternCall(List<PConstraintInfo> resultList, | ||
111 | PositivePatternCall pCall) { | ||
112 | // A pattern call can have any of its variables unbound | ||
113 | Set<PVariable> affectedVariables = pCall.getAffectedVariables(); | ||
114 | // IN parameters cannot be unbound and | ||
115 | // OUT parameters cannot be bound | ||
116 | Tuple variables = pCall.getVariablesTuple(); | ||
117 | final Set<PVariable> inVariables = new HashSet<>(); | ||
118 | Set<PVariable> inoutVariables = new HashSet<>(); | ||
119 | List<PParameter> parameters = pCall.getReferredQuery().getParameters(); | ||
120 | for(int i=0;i<parameters.size();i++){ | ||
121 | switch(parameters.get(i).getDirection()){ | ||
122 | case IN: | ||
123 | inVariables.add((PVariable) variables.get(i)); | ||
124 | break; | ||
125 | case INOUT: | ||
126 | inoutVariables.add((PVariable) variables.get(i)); | ||
127 | break; | ||
128 | case OUT: | ||
129 | default: | ||
130 | break; | ||
131 | |||
132 | } | ||
133 | } | ||
134 | Iterable<Set<PVariable>> bindings = Sets.powerSet(inoutVariables).stream() | ||
135 | .map(input -> Stream.concat(input.stream(), inVariables.stream()).collect(Collectors.toSet())) | ||
136 | .collect(Collectors.toSet()); | ||
137 | |||
138 | doCreateConstraintInfos(resultList, pCall, affectedVariables, bindings); | ||
139 | } | ||
140 | |||
141 | private void createConstraintInfoBinaryTransitiveClosure(List<PConstraintInfo> resultList, | ||
142 | AbstractTransitiveClosure closure) { | ||
143 | // A pattern call can have any of its variables unbound | ||
144 | |||
145 | List<PParameter> parameters = closure.getReferredQuery().getParameters(); | ||
146 | Tuple variables = closure.getVariablesTuple(); | ||
147 | |||
148 | Set<Set<PVariable>> bindings = new HashSet<>(); | ||
149 | PVariable firstVariable = (PVariable) variables.get(0); | ||
150 | PVariable secondVariable = (PVariable) variables.get(1); | ||
151 | // Check is always supported | ||
152 | bindings.add(new HashSet<>(Arrays.asList(firstVariable, secondVariable))); | ||
153 | // If first parameter is not bound mandatorily, it can be left out | ||
154 | if (parameters.get(0).getDirection() != PParameterDirection.IN) { | ||
155 | bindings.add(Collections.singleton(secondVariable)); | ||
156 | } | ||
157 | // If second parameter is not bound mandatorily, it can be left out | ||
158 | if (parameters.get(1).getDirection() != PParameterDirection.IN) { | ||
159 | bindings.add(Collections.singleton(firstVariable)); | ||
160 | } | ||
161 | |||
162 | doCreateConstraintInfos(resultList, closure, closure.getAffectedVariables(), bindings); | ||
163 | } | ||
164 | |||
165 | |||
166 | |||
167 | private void createConstraintInfoExportedParameter(List<PConstraintInfo> resultList, | ||
168 | ExportedParameter parameter) { | ||
169 | // In case of an exported parameter constraint, the parameter must be bound in order to execute | ||
170 | Set<PVariable> affectedVariables = parameter.getAffectedVariables(); | ||
171 | doCreateConstraintInfos(resultList, parameter, affectedVariables, Collections.singleton(affectedVariables)); | ||
172 | } | ||
173 | |||
174 | private void createConstraintInfoExpressionEvaluation(List<PConstraintInfo> resultList, | ||
175 | ExpressionEvaluation expressionEvaluation) { | ||
176 | // An expression evaluation can only have its output variable unbound. All other variables shall be bound | ||
177 | PVariable output = expressionEvaluation.getOutputVariable(); | ||
178 | Set<Set<PVariable>> bindings = new HashSet<>(); | ||
179 | Set<PVariable> affectedVariables = expressionEvaluation.getAffectedVariables(); | ||
180 | // All variables bound -> check | ||
181 | bindings.add(affectedVariables); | ||
182 | // Output variable is not bound -> extend | ||
183 | bindings.add(affectedVariables.stream().filter(var -> !Objects.equals(var, output)).collect(Collectors.toSet())); | ||
184 | doCreateConstraintInfos(resultList, expressionEvaluation, affectedVariables, bindings); | ||
185 | } | ||
186 | |||
187 | private void createConstraintInfoTypeFilterConstraint(List<PConstraintInfo> resultList, | ||
188 | TypeFilterConstraint filter){ | ||
189 | // In case of type filter, all affected variables must be bound in order to execute | ||
190 | Set<PVariable> affectedVariables = filter.getAffectedVariables(); | ||
191 | doCreateConstraintInfos(resultList, filter, affectedVariables, Collections.singleton(affectedVariables)); | ||
192 | } | ||
193 | |||
194 | private void createConstraintInfoInequality(List<PConstraintInfo> resultList, | ||
195 | Inequality inequality){ | ||
196 | // In case of inequality, all affected variables must be bound in order to execute | ||
197 | Set<PVariable> affectedVariables = inequality.getAffectedVariables(); | ||
198 | doCreateConstraintInfos(resultList, inequality, affectedVariables, Collections.singleton(affectedVariables)); | ||
199 | } | ||
200 | |||
201 | private void createConstraintInfoAggregatorConstraint(List<PConstraintInfo> resultList, | ||
202 | PConstraint pConstraint, PVariable resultVariable){ | ||
203 | Set<PVariable> affectedVariables = pConstraint.getAffectedVariables(); | ||
204 | |||
205 | // The only variables which can be unbound are single-use | ||
206 | Set<PVariable> canBeUnboundVariables = | ||
207 | Stream.concat(Stream.of(resultVariable), affectedVariables.stream().filter(SINGLE_USE_VARIABLE)).collect(Collectors.toSet()); | ||
208 | |||
209 | Set<Set<PVariable>> bindings = calculatePossibleBindings(canBeUnboundVariables, affectedVariables); | ||
210 | |||
211 | doCreateConstraintInfos(resultList, pConstraint, affectedVariables, bindings); | ||
212 | } | ||
213 | |||
214 | /** | ||
215 | * | ||
216 | * @param canBeUnboundVariables Variables which are allowed to be unbound | ||
217 | * @param affectedVariables All affected variables | ||
218 | * @return The set of possible bound variable sets | ||
219 | */ | ||
220 | private Set<Set<PVariable>> calculatePossibleBindings(Set<PVariable> canBeUnboundVariables, Set<PVariable> affectedVariables){ | ||
221 | final Set<PVariable> mustBindVariables = affectedVariables.stream().filter(input -> !canBeUnboundVariables.contains(input)).collect(Collectors.toSet()); | ||
222 | return Sets.powerSet(canBeUnboundVariables).stream() | ||
223 | .map(input -> { | ||
224 | //some variables have to be bound before executing this constraint | ||
225 | Set<PVariable> result= new HashSet<>(input); | ||
226 | result.addAll(mustBindVariables); | ||
227 | return result; | ||
228 | }) | ||
229 | .collect(Collectors.toSet()); | ||
230 | } | ||
231 | |||
232 | private void createConstraintInfoGeneric(List<PConstraintInfo> resultList, PConstraint pConstraint){ | ||
233 | Set<PVariable> affectedVariables = pConstraint.getAffectedVariables(); | ||
234 | |||
235 | // The only variables which can be unbound are single use variables | ||
236 | Set<PVariable> canBeUnboundVariables = affectedVariables.stream().filter(SINGLE_USE_VARIABLE).collect(Collectors.toSet()); | ||
237 | |||
238 | Set<Set<PVariable>> bindings = calculatePossibleBindings(canBeUnboundVariables, affectedVariables); | ||
239 | |||
240 | doCreateConstraintInfos(resultList, pConstraint, affectedVariables, bindings); | ||
241 | } | ||
242 | |||
243 | private void createConstraintInfoTypeConstraint(List<PConstraintInfo> resultList, | ||
244 | TypeConstraint typeConstraint) { | ||
245 | Set<PVariable> affectedVariables = typeConstraint.getAffectedVariables(); | ||
246 | Set<? extends Set<PVariable>> bindings = null; | ||
247 | |||
248 | IInputKey inputKey = typeConstraint.getSupplierKey(); | ||
249 | if(inputKey.isEnumerable()){ | ||
250 | bindings = Sets.powerSet(affectedVariables); | ||
251 | }else{ | ||
252 | // For not enumerable types, this constraint can only be a check | ||
253 | bindings = Collections.singleton(affectedVariables); | ||
254 | } | ||
255 | |||
256 | doCreateConstraintInfos(resultList, typeConstraint, affectedVariables, bindings); | ||
257 | } | ||
258 | |||
259 | private void doCreateConstraintInfos(List<PConstraintInfo> constraintInfos, | ||
260 | PConstraint pConstraint, Set<PVariable> affectedVariables, Iterable<? extends Set<PVariable>> bindings) { | ||
261 | Set<PConstraintInfo> sameWithDifferentBindings = new HashSet<>(); | ||
262 | for (Set<PVariable> boundVariables : bindings) { | ||
263 | |||
264 | PConstraintInfo info = new PConstraintInfo(pConstraint, boundVariables, | ||
265 | affectedVariables.stream().filter(input -> !boundVariables.contains(input)).collect(Collectors.toSet()), | ||
266 | sameWithDifferentBindings, context, resultRequestor, costFunction); | ||
267 | constraintInfos.add(info); | ||
268 | sameWithDifferentBindings.add(info); | ||
269 | } | ||
270 | } | ||
271 | |||
272 | private Set<Set<PVariable>> excludeUnnavigableOperationMasks(TypeConstraint typeConstraint, Set<? extends Set<PVariable>> bindings) { | ||
273 | PVariable firstVariable = typeConstraint.getVariableInTuple(0); | ||
274 | return bindings.stream().filter( | ||
275 | boundVariablesSet -> (boundVariablesSet.isEmpty() || boundVariablesSet.contains(firstVariable))) | ||
276 | .collect(Collectors.toSet()); | ||
277 | } | ||
278 | } | ||