/
TaskInsertion.java
233 lines (201 loc) · 9.73 KB
/
TaskInsertion.java
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
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
package org.metaborg.runtime.task;
import static org.metaborg.runtime.task.util.InvokeStrategy.invoke;
import static org.metaborg.runtime.task.util.TermTools.makeList;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Map.Entry;
import java.util.Set;
import org.metaborg.runtime.task.util.SingletonIterable;
import org.spoofax.interpreter.core.IContext;
import org.spoofax.interpreter.library.ssl.StrategoHashMap;
import org.spoofax.interpreter.stratego.Strategy;
import org.spoofax.interpreter.terms.IStrategoAppl;
import org.spoofax.interpreter.terms.IStrategoTerm;
import org.spoofax.interpreter.terms.ITermFactory;
import com.google.common.collect.ArrayListMultimap;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;
import com.google.common.collect.Multimap;
import com.google.common.collect.Sets;
import fj.P;
import fj.P2;
import fj.data.Either;
public final class TaskInsertion {
/**
* Returns all instruction permutations of given task based on its dependencies. For regular tasks,
* {@link #insertResultCombinations} is called. For task combinators, {@link #insertResultLists} is called. This
* function assumes that all dependencies of the given task have been solved (have a result or failed).
*/
public static P2<? extends Iterable<IStrategoTerm>, Boolean> taskCombinations(ITermFactory factory,
ITaskEngine taskEngine, IContext context, Strategy collect, Strategy insert, IStrategoTerm taskID, Task task) {
final IStrategoTerm instruction = task.instruction;
final Iterable<IStrategoTerm> actualDependencies = getResultIDs(context, collect, instruction);
final Iterable<IStrategoTerm> allDependencies = taskEngine.getDependencies(taskID);
if(Iterables.isEmpty(allDependencies)) {
return P.p(new SingletonIterable<IStrategoTerm>(instruction), false);
} else if(!task.isCombinator) {
for(IStrategoTerm dependencyID : allDependencies) {
final Task dependency = taskEngine.getTask(dependencyID);
if(dependency.failed() || !dependency.hasResults()) {
return null; // If a dependency does not have any results, the task cannot be executed.
}
}
return insertResultCombinations(taskEngine, context, collect, insert, instruction, actualDependencies,
new SingletonIterable<IStrategoTerm>(taskID));
} else {
return P.p(
new SingletonIterable<IStrategoTerm>(insertResultLists(factory, taskEngine, context, insert,
instruction, actualDependencies)), false);
}
}
/**
* Returns term permutations, or dynamic dependencies encountered while creating the term permutations. To create
* all permutations, a cartesian product of all results of task dependencies is created and applied to the term.
*
* If all task dependencies have only one result, this will result in just one term. Otherwise multiple terms are
* returned. If a task dependency has failed or has no results, null is returned instead. If dynamic task
* dependencies are encountered, the resulting iterable contains task IDs of these dependencies.
*
* @param taskEngine The task engine to retrieve tasks from.
* @param context A Stratego context for executing strategies.
* @param collect Collect strategy that collects all result IDs in a term.
* @param insert Insert strategy that inserts results into a term.
* @param term The term to create permutations for.
* @param dependencies The task IDs of tasks this term depends on.
*
* @return A 2-pair. If the second element is false, the first element contains permutations of the term. Otherwise
* it contains task IDs of dynamic task dependencies.
*/
public static P2<? extends Iterable<IStrategoTerm>, Boolean> insertResultCombinations(ITaskEngine taskEngine,
IContext context, Strategy collect, Strategy insert, IStrategoTerm term, Iterable<IStrategoTerm> dependencies,
Iterable<IStrategoTerm> initialSeen) {
final Set<IStrategoTerm> seen = Sets.newHashSet(initialSeen);
final Either<Multimap<IStrategoTerm, IStrategoTerm>, ? extends Iterable<IStrategoTerm>> result =
createResultMapping(taskEngine, context, collect, insert, dependencies, seen);
if(result == null) {
return null;
} else if(result.isRight()) {
return P.p(result.right().value(), true);
} else {
return P.p(insertCarthesianProduct(context, insert, term, result.left().value()), false);
}
}
private static Either<Multimap<IStrategoTerm, IStrategoTerm>, ? extends Iterable<IStrategoTerm>>
createResultMapping(ITaskEngine taskEngine, IContext context, Strategy collect, Strategy insert,
Iterable<IStrategoTerm> resultIDs, Set<IStrategoTerm> seen) {
final Multimap<IStrategoTerm, IStrategoTerm> resultsMap = ArrayListMultimap.create();
final Collection<IStrategoTerm> dynamicDependencies = Lists.newLinkedList();
for(final IStrategoTerm resultID : resultIDs) {
if(seen.contains(resultID)) {
resultsMap.put(resultID, createCycleTerm(context.getFactory(), resultID));
continue;
}
final Either<Collection<IStrategoTerm>, ? extends Iterable<IStrategoTerm>> results =
getResultsOf(taskEngine, context, collect, insert, resultID, Sets.newHashSet(seen));
if(results == null) {
return null;
} else if(results.isRight()) {
Iterables.addAll(dynamicDependencies, results.right().value());
} else {
resultsMap.putAll(resultID, results.left().value());
}
}
if(dynamicDependencies.isEmpty())
return Either.left(resultsMap);
else
return Either.right(dynamicDependencies);
}
private static Either<Collection<IStrategoTerm>, ? extends Iterable<IStrategoTerm>> getResultsOf(
ITaskEngine taskEngine, IContext context, Strategy collect, Strategy insert, IStrategoTerm taskID,
Set<IStrategoTerm> seen) {
seen.add(taskID);
final Task task = taskEngine.getTask(taskID);
if(!task.solved()) {
return Either.right(new SingletonIterable<IStrategoTerm>(taskID));
} else if(task.failed() || !task.hasResults()) {
return null; // If a dependency does not have any results, the task cannot be executed.
}
final Collection<IStrategoTerm> results = Lists.newLinkedList();
final Collection<IStrategoTerm> dynamicDependencies = Lists.newLinkedList();
for(final IStrategoTerm result : task.results()) {
final Iterable<IStrategoTerm> nestedResultIDs = getResultIDs(context, collect, result);
if(Iterables.isEmpty(nestedResultIDs)) {
results.add(result);
} else {
final Either<Multimap<IStrategoTerm, IStrategoTerm>, ? extends Iterable<IStrategoTerm>> resultMapping =
createResultMapping(taskEngine, context, collect, insert, nestedResultIDs, seen);
if(resultMapping == null) {
return null;
} else if(resultMapping.isRight()) {
Iterables.addAll(dynamicDependencies, resultMapping.right().value());
} else {
final Collection<IStrategoTerm> insertedResults =
insertCarthesianProduct(context, insert, result, resultMapping.left().value());
results.addAll(insertedResults);
}
}
}
if(dynamicDependencies.isEmpty())
return Either.left(results);
else
return Either.right(dynamicDependencies);
}
private static Collection<IStrategoTerm> insertCarthesianProduct(IContext context, Strategy insert,
IStrategoTerm term, Multimap<IStrategoTerm, IStrategoTerm> resultMapping) {
final Collection<StrategoHashMap> resultCombinations = cartesianProduct(resultMapping);
final Collection<IStrategoTerm> instructions = Lists.newLinkedList();
for(StrategoHashMap mapping : resultCombinations) {
instructions.add(insertResults(context, insert, term, mapping));
}
return instructions;
}
/**
* Returns an iterable that only has one instruction where the results have been inserted as lists.
*/
private static IStrategoTerm insertResultLists(ITermFactory factory, ITaskEngine taskEngine, IContext context,
Strategy insert, IStrategoTerm term, Iterable<IStrategoTerm> resultIDs) {
final StrategoHashMap mapping = new StrategoHashMap();
for(IStrategoTerm resultID : resultIDs) {
final Task task = taskEngine.getTask(resultID);
mapping.put(resultID, makeList(factory, task.results()));
}
final IStrategoTerm insertedTerm = insertResults(context, insert, term, mapping);
return insertedTerm;
}
/**
* Given a multimap from task identifiers to their results, returns the cartesian product of that mapping. The
* product is returned as a collection of maps that map task identifiers to one result.
*/
public static Collection<StrategoHashMap> cartesianProduct(Multimap<IStrategoTerm, IStrategoTerm> results) {
Collection<StrategoHashMap> result = new ArrayList<StrategoHashMap>();
if(results.size() > 0)
result.add(new StrategoHashMap());
for(Entry<IStrategoTerm, Collection<IStrategoTerm>> entry : results.asMap().entrySet()) {
Collection<StrategoHashMap> newResults = new ArrayList<StrategoHashMap>();
for(StrategoHashMap map : result) {
for(IStrategoTerm val : entry.getValue()) {
StrategoHashMap mapping = new StrategoHashMap();
mapping.putAll(map);
mapping.put(entry.getKey(), val);
newResults.add(mapping);
}
}
result = newResults;
}
return result;
}
private static Iterable<IStrategoTerm> getResultIDs(IContext context, Strategy collect, IStrategoTerm term) {
return invoke(context, collect, term);
}
private static IStrategoTerm insertResults(IContext context, Strategy insertResults, IStrategoTerm instruction,
StrategoHashMap resultCombinations) {
return invoke(context, insertResults, instruction,
createHashtableTerm(context.getFactory(), resultCombinations));
}
private static IStrategoAppl createHashtableTerm(ITermFactory factory, StrategoHashMap hashMap) {
return factory.makeAppl(factory.makeConstructor("Hashtable", 1), hashMap);
}
private static IStrategoAppl createCycleTerm(ITermFactory factory, IStrategoTerm taskID) {
return factory.makeAppl(factory.makeConstructor("CYCLIC_INSERTION", 1), taskID);
}
}