1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
|
/*******************************************************************************
* Copyright (c) 2004-2010 Gabor Bergmann and Daniel Varro
* This program and the accompanying materials are made available under the
* terms of the Eclipse Public License v. 2.0 which is available at
* http://www.eclipse.org/legal/epl-v20.html.
*
* SPDX-License-Identifier: EPL-2.0
*******************************************************************************/
package tools.refinery.viatra.runtime.matchers.planning.helpers;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Queue;
import java.util.Set;
import java.util.stream.Collectors;
import tools.refinery.viatra.runtime.matchers.context.IInputKey;
import tools.refinery.viatra.runtime.matchers.context.IQueryMetaContext;
import tools.refinery.viatra.runtime.matchers.psystem.ITypeInfoProviderConstraint;
import tools.refinery.viatra.runtime.matchers.psystem.PConstraint;
import tools.refinery.viatra.runtime.matchers.psystem.PVariable;
import tools.refinery.viatra.runtime.matchers.psystem.TypeJudgement;
/**
* @author Gabor Bergmann
* @author Tamas Szabo
*/
public class TypeHelper {
private TypeHelper() {
// Hiding constructor for utility class
}
/**
* Collects the type constraints for the specified collection of variables. The type constraints consist of the
* constraints directly enforced on the variable itself, plus all of those that the given variable is unified with
* through equalities.
*
* @param variables
* the variables in question
* @param constraints
* the constraints in the pattern body
* @param context
* the query meta context
* @return the mapping from variable to set of type constraints
* @since 1.6
*/
public static Map<PVariable, Set<IInputKey>> inferUnaryTypesFor(Iterable<PVariable> variables,
Set<PConstraint> constraints, IQueryMetaContext context) {
Map<PVariable, Set<TypeJudgement>> typeMap = TypeHelper.inferUnaryTypes(constraints, context);
return inferUnaryTypesFor(variables, typeMap);
}
/**
* Collects the type constraints for the specified collection of variables. The type constraints consist of the
* constraints directly enforced on the variable itself, plus all of those that the given variable is unified with
* through equalities.
*
* The method accepts a type map which is the result of the basic type inference from the
* {@link TypeHelper.inferUnaryTypes} method. The purpose of this method is that the type map can be reused across
* several calls to this method.
*
* @param variables
* the variables in question
* @param typeMap
* the type map of inference results
* @return the mapping from variable to set of type constraints
* @since 1.6
*/
public static Map<PVariable, Set<IInputKey>> inferUnaryTypesFor(Iterable<PVariable> variables,
Map<PVariable, Set<TypeJudgement>> typeMap) {
Map<PVariable, Set<IInputKey>> result = new HashMap<PVariable, Set<IInputKey>>();
for (PVariable original : variables) {
// it can happen that the variable was unified into an other one due to equalities
Set<IInputKey> keys = new HashSet<IInputKey>();
PVariable current = original;
while (current != null) {
Set<TypeJudgement> judgements = typeMap.get(current);
if (judgements != null) {
for (TypeJudgement judgement : judgements) {
keys.add(judgement.getInputKey());
}
}
current = current.getDirectUnifiedInto();
}
result.put(original, keys);
}
return result;
}
/**
* Infers unary type information for variables, based on the given constraints.
*
* Subsumptions are not taken into account.
*
* @param constraints
* the set of constraints to extract type info from
*/
public static Map<PVariable, Set<TypeJudgement>> inferUnaryTypes(Set<PConstraint> constraints,
IQueryMetaContext context) {
Set<TypeJudgement> equivalentJudgements = getDirectJudgements(constraints, context);
Set<TypeJudgement> impliedJudgements = typeClosure(equivalentJudgements, context);
Map<PVariable, Set<TypeJudgement>> results = new HashMap<PVariable, Set<TypeJudgement>>();
for (TypeJudgement typeJudgement : impliedJudgements) {
final IInputKey inputKey = typeJudgement.getInputKey();
if (inputKey.getArity() == 1) {
PVariable variable = (PVariable) typeJudgement.getVariablesTuple().get(0);
Set<TypeJudgement> inferredTypes = results.computeIfAbsent(variable, v -> new HashSet<>());
inferredTypes.add(typeJudgement);
}
}
return results;
}
/**
* Gets direct judgements reported by constraints. No closure is applied yet.
*/
public static Set<TypeJudgement> getDirectJudgements(Set<PConstraint> constraints, IQueryMetaContext context) {
Set<TypeJudgement> equivalentJudgements = new HashSet<TypeJudgement>();
for (PConstraint pConstraint : constraints) {
if (pConstraint instanceof ITypeInfoProviderConstraint) {
equivalentJudgements.addAll(((ITypeInfoProviderConstraint) pConstraint).getImpliedJudgements(context));
}
}
return equivalentJudgements;
}
/**
* Calculates the closure of a set of type judgements, with respect to supertyping.
*
* @return the set of all type judgements in typesToClose and all their direct and indirect supertypes
*/
public static Set<TypeJudgement> typeClosure(Set<TypeJudgement> typesToClose, IQueryMetaContext context) {
return typeClosure(Collections.<TypeJudgement> emptySet(), typesToClose, context);
}
/**
* Calculates the closure of a set of type judgements (with respect to supertyping), where the closure has been
* calculated before for a given base set, but not for a separate delta set.
* <p>
* Precondition: the set (typesToClose MINUS delta) is already closed w.r.t. supertyping.
*
* @return the set of all type judgements in typesToClose and all their direct and indirect supertypes
* @since 1.6
*/
public static Set<TypeJudgement> typeClosure(Set<TypeJudgement> preclosedBaseSet, Set<TypeJudgement> delta,
IQueryMetaContext context) {
Queue<TypeJudgement> queue = delta.stream().filter(input -> !preclosedBaseSet.contains(input)).collect(Collectors.toCollection(LinkedList::new));
if (queue.isEmpty())
return preclosedBaseSet;
Set<TypeJudgement> closure = new HashSet<TypeJudgement>(preclosedBaseSet);
Map<TypeJudgement, Set<TypeJudgement>> conditionalImplications = new HashMap<>();
for (TypeJudgement typeJudgement : closure) {
conditionalImplications.putAll(typeJudgement.getConditionalImpliedJudgements(context));
}
do {
TypeJudgement deltaType = queue.poll();
if (closure.add(deltaType)) {
// direct implications
queue.addAll(deltaType.getDirectlyImpliedJudgements(context));
// conditional implications, source key processed before, this is the condition key
final Set<TypeJudgement> implicationSet = conditionalImplications.get(deltaType);
if (implicationSet != null) {
queue.addAll(implicationSet);
}
// conditional implications, this is the source key
Map<TypeJudgement, Set<TypeJudgement>> deltaConditionalImplications = deltaType
.getConditionalImpliedJudgements(context);
for (Entry<TypeJudgement, Set<TypeJudgement>> entry : deltaConditionalImplications.entrySet()) {
if (closure.contains(entry.getKey())) {
// condition processed before
queue.addAll(entry.getValue());
} else {
// condition not processed yet
conditionalImplications.computeIfAbsent(entry.getKey(), key -> new HashSet<>())
.addAll(entry.getValue());
}
}
}
} while (!queue.isEmpty());
return closure;
}
/**
* Calculates a remainder set of types from a larger set, that are not subsumed by a given set of subsuming types.
*
* @param subsumableTypes
* a set of types from which some may be implied by the subsuming types
* @param subsumingTypes
* a set of types that may imply some of the subsuming types
* @return the collection of types in subsumableTypes that are NOT identical to or supertypes of any type in
* subsumingTypes.
*/
public static Set<TypeJudgement> subsumeTypes(Set<TypeJudgement> subsumableTypes, Set<TypeJudgement> subsumingTypes,
IQueryMetaContext context) {
Set<TypeJudgement> closure = typeClosure(subsumingTypes, context);
Set<TypeJudgement> subsumed = new HashSet<TypeJudgement>(subsumableTypes);
subsumed.removeAll(closure);
return subsumed;
}
}
|
