1 | // Copyright 2012 Georg-August-Universität Göttingen, Germany
|
---|
2 | //
|
---|
3 | // Licensed under the Apache License, Version 2.0 (the "License");
|
---|
4 | // you may not use this file except in compliance with the License.
|
---|
5 | // You may obtain a copy of the License at
|
---|
6 | //
|
---|
7 | // http://www.apache.org/licenses/LICENSE-2.0
|
---|
8 | //
|
---|
9 | // Unless required by applicable law or agreed to in writing, software
|
---|
10 | // distributed under the License is distributed on an "AS IS" BASIS,
|
---|
11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
---|
12 | // See the License for the specific language governing permissions and
|
---|
13 | // limitations under the License.
|
---|
14 |
|
---|
15 | package de.ugoe.cs.autoquest.commands.usability;
|
---|
16 |
|
---|
17 | import java.io.PrintStream;
|
---|
18 | import java.util.ArrayList;
|
---|
19 | import java.util.Collection;
|
---|
20 | import java.util.HashMap;
|
---|
21 | import java.util.HashSet;
|
---|
22 | import java.util.IdentityHashMap;
|
---|
23 | import java.util.Iterator;
|
---|
24 | import java.util.LinkedList;
|
---|
25 | import java.util.List;
|
---|
26 | import java.util.Map;
|
---|
27 | import java.util.Set;
|
---|
28 | import java.util.Stack;
|
---|
29 |
|
---|
30 | import de.ugoe.cs.autoquest.CommandHelpers;
|
---|
31 | import de.ugoe.cs.autoquest.eventcore.IEventTarget;
|
---|
32 | import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
|
---|
33 | import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskHandlingStrategy;
|
---|
34 | import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskInstanceTraversingVisitor;
|
---|
35 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask;
|
---|
36 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance;
|
---|
37 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
|
---|
38 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional;
|
---|
39 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
|
---|
40 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
|
---|
41 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
|
---|
42 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
|
---|
43 | import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskModel;
|
---|
44 | import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
|
---|
45 | import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskTreeUtils;
|
---|
46 | import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
|
---|
47 | import de.ugoe.cs.util.console.Command;
|
---|
48 | import de.ugoe.cs.util.console.Console;
|
---|
49 | import de.ugoe.cs.util.console.GlobalDataContainer;
|
---|
50 |
|
---|
51 | /**
|
---|
52 | * <p>
|
---|
53 | * compares a set of task models with each other and drops their similarity as results
|
---|
54 | * </p>
|
---|
55 | *
|
---|
56 | * @author Patrick Harms
|
---|
57 | * @version 1.0
|
---|
58 | */
|
---|
59 | public class CMDgetTaskModelCrossCoverage implements Command {
|
---|
60 |
|
---|
61 | /** */
|
---|
62 | private static Object EOF = new Object();
|
---|
63 |
|
---|
64 | /*
|
---|
65 | * (non-Javadoc)
|
---|
66 | *
|
---|
67 | * @see de.ugoe.cs.util.console.Command#help()
|
---|
68 | */
|
---|
69 | @Override
|
---|
70 | public String help() {
|
---|
71 | return "getTaskModelCrossCoverage <tasktree1> <tasktree2> ...";
|
---|
72 | }
|
---|
73 |
|
---|
74 | /*
|
---|
75 | * (non-Javadoc)
|
---|
76 | *
|
---|
77 | * @see de.ugoe.cs.util.console.Command#run(java.util.List)
|
---|
78 | */
|
---|
79 | @Override
|
---|
80 | public void run(List<Object> parameters) {
|
---|
81 | List<String> inputTaskTreeNames = new LinkedList<>();
|
---|
82 |
|
---|
83 | try {
|
---|
84 | for (Object param : parameters) {
|
---|
85 | inputTaskTreeNames.add((String) param);
|
---|
86 | }
|
---|
87 | }
|
---|
88 | catch (Exception e) {
|
---|
89 | throw new IllegalArgumentException("must provide valid input task tree names");
|
---|
90 | }
|
---|
91 |
|
---|
92 | Map<ITaskModel, List<List<IEventTask>>> inputTaskModels = new IdentityHashMap<>();
|
---|
93 | ITaskModel firstModel = null;
|
---|
94 | final SymbolMap<ITask, IEventTask> eventTasksOfFirstModel =
|
---|
95 | new TaskHandlingStrategy(TaskEquality.SEMANTICALLY_EQUAL).createSymbolMap();
|
---|
96 |
|
---|
97 |
|
---|
98 | for (String inputTaskTreeName : inputTaskTreeNames) {
|
---|
99 | Object dataObject = GlobalDataContainer.getInstance().getData(inputTaskTreeName);
|
---|
100 | if (dataObject == null) {
|
---|
101 | CommandHelpers.objectNotFoundMessage(inputTaskTreeName);
|
---|
102 | continue;
|
---|
103 | }
|
---|
104 | if (!(dataObject instanceof ITaskModel)) {
|
---|
105 | CommandHelpers.objectNotType(inputTaskTreeName, "ITaskModel");
|
---|
106 | continue;
|
---|
107 | }
|
---|
108 |
|
---|
109 | System.out.println("preparing sessions to check for " + dataObject);
|
---|
110 | List<List<IEventTask>> sessionsToCheck = new LinkedList<>();
|
---|
111 | final Map<IEventTask, IEventTask> identityMap = new IdentityHashMap<>();
|
---|
112 |
|
---|
113 | for (IUserSession session : ((ITaskModel) dataObject).getUserSessions()) {
|
---|
114 | final List<IEventTask> eventTasks = new ArrayList<>();
|
---|
115 | for (ITaskInstance instance : session) {
|
---|
116 | instance.accept(new DefaultTaskInstanceTraversingVisitor() {
|
---|
117 | @Override
|
---|
118 | public void visit(IEventTaskInstance eventTaskInstance) {
|
---|
119 | IEventTask eventTask = eventTaskInstance.getEventTask();
|
---|
120 | IEventTask replacement = identityMap.get(eventTask);
|
---|
121 |
|
---|
122 | if (replacement == null) {
|
---|
123 | replacement = eventTasksOfFirstModel.getValue(eventTask);
|
---|
124 |
|
---|
125 | if (replacement == null) {
|
---|
126 | replacement = eventTaskInstance.getEventTask();
|
---|
127 | eventTasksOfFirstModel.addSymbol(replacement, replacement);
|
---|
128 | }
|
---|
129 |
|
---|
130 | identityMap.put(eventTask, replacement);
|
---|
131 | }
|
---|
132 |
|
---|
133 | eventTasks.add(replacement);
|
---|
134 | }
|
---|
135 | });
|
---|
136 | }
|
---|
137 |
|
---|
138 | sessionsToCheck.add(eventTasks);
|
---|
139 | }
|
---|
140 |
|
---|
141 | inputTaskModels.put((ITaskModel) dataObject, sessionsToCheck);
|
---|
142 |
|
---|
143 | if (firstModel == null) {
|
---|
144 | firstModel = (ITaskModel) dataObject;
|
---|
145 | }
|
---|
146 | }
|
---|
147 |
|
---|
148 | getTaskModelCrossCoverage(firstModel, inputTaskModels);
|
---|
149 | }
|
---|
150 |
|
---|
151 | /**
|
---|
152 | *
|
---|
153 | */
|
---|
154 | private void getTaskModelCrossCoverage(ITaskModel modelToCompare,
|
---|
155 | Map<ITaskModel, List<List<IEventTask>>> sessionsToCheck)
|
---|
156 | {
|
---|
157 | System.out.println("creating parsing tables for " + modelToCompare);
|
---|
158 | List<ParsingTable> parsingTables = getParsingTables(modelToCompare);
|
---|
159 |
|
---|
160 | for (Map.Entry<ITaskModel, List<List<IEventTask>>> entry : sessionsToCheck.entrySet()) {
|
---|
161 | if (entry.getKey() != modelToCompare) {
|
---|
162 | System.out.println("performing parsing against " + entry.getKey());
|
---|
163 | Statistics statistics = new Statistics(modelToCompare, entry.getKey());
|
---|
164 |
|
---|
165 | parse(entry.getValue(), parsingTables, statistics);
|
---|
166 |
|
---|
167 | statistics.dump(System.out);
|
---|
168 | }
|
---|
169 | }
|
---|
170 | }
|
---|
171 |
|
---|
172 | /**
|
---|
173 | *
|
---|
174 | */
|
---|
175 | private List<ParsingTable> getParsingTables(ITaskModel forTaskModel) {
|
---|
176 | List<ProductionRule> rules = new LinkedList<>();
|
---|
177 |
|
---|
178 | for (ITask task : forTaskModel.getTasks()) {
|
---|
179 | if (task instanceof ISequence) {
|
---|
180 | // other task types will be handled implicitly
|
---|
181 | addRulesIfNotThere(rules, createProductionRules((ISequence) task));
|
---|
182 | }
|
---|
183 | }
|
---|
184 |
|
---|
185 | List<ParsingTable> tables = new ArrayList<ParsingTable>();
|
---|
186 |
|
---|
187 | int count = 0;
|
---|
188 | for (ITask task : forTaskModel.getTasks()) {
|
---|
189 | if (task instanceof ISequence) {
|
---|
190 | try {
|
---|
191 | tables.add(createParsingTable((ISequence) task, getRelevantRules(task, rules)));
|
---|
192 | }
|
---|
193 | catch (IllegalArgumentException e) {
|
---|
194 | Console.println(e.toString() + " " + ++count);
|
---|
195 | }
|
---|
196 | }
|
---|
197 | }
|
---|
198 |
|
---|
199 | return tables;
|
---|
200 | }
|
---|
201 |
|
---|
202 | /**
|
---|
203 | *
|
---|
204 | */
|
---|
205 | private List<ProductionRule> createProductionRules(ISequence sequence) {
|
---|
206 | //new TaskTreeEncoder().encode(sequence, System.out);
|
---|
207 |
|
---|
208 | List<ProductionRule> rules = new LinkedList<ProductionRule>();
|
---|
209 |
|
---|
210 | List<ExecutionVariants> executionVariants = new ArrayList<>(sequence.getChildren().size());
|
---|
211 | int noOfOptionalChildren = 0;
|
---|
212 |
|
---|
213 | for (ITask child : sequence.getChildren()) {
|
---|
214 | ExecutionVariants variants = getExecutionVariants(child);
|
---|
215 | if (variants.canBeOptional()) {
|
---|
216 | noOfOptionalChildren++;
|
---|
217 | }
|
---|
218 | executionVariants.add(variants);
|
---|
219 | }
|
---|
220 |
|
---|
221 | // for iterations and selections, we create non terminals
|
---|
222 | // for optional children, we create multiple production for the current sequence
|
---|
223 | // all other children are just added
|
---|
224 |
|
---|
225 | for (int i = 0; i < Math.pow(2, noOfOptionalChildren); i++) {
|
---|
226 | int childIndex = 0;
|
---|
227 | int optionalIndex = 0;
|
---|
228 | List<Object> rightHandSide = new ArrayList<>();
|
---|
229 |
|
---|
230 | for (ITask child : sequence.getChildren()) {
|
---|
231 | boolean leaveout = false;
|
---|
232 | if (child instanceof IEventTask) {
|
---|
233 | rightHandSide.add(child);
|
---|
234 | childIndex++;
|
---|
235 | continue;
|
---|
236 | }
|
---|
237 | else if (executionVariants.get(childIndex).canBeOptional()) {
|
---|
238 | // child is optional, check if to be left out
|
---|
239 | if ((((int) Math.pow(2, optionalIndex)) & i) == 0) {
|
---|
240 | leaveout = true;
|
---|
241 | }
|
---|
242 |
|
---|
243 | optionalIndex++;
|
---|
244 | }
|
---|
245 |
|
---|
246 | if (leaveout) {
|
---|
247 | childIndex++;
|
---|
248 | continue;
|
---|
249 | }
|
---|
250 |
|
---|
251 | Object childSymbol = null;
|
---|
252 |
|
---|
253 | if (executionVariants.get(childIndex).size() > 1) {
|
---|
254 | // create selective production rules
|
---|
255 | childSymbol = sequence.getId() + "_sel" + childIndex;
|
---|
256 |
|
---|
257 | int variantIndex = 0;
|
---|
258 | for (ExecutionVariant executionVariant : executionVariants.get(childIndex)) {
|
---|
259 | if (!executionVariant.canBeIterated) {
|
---|
260 | rules.add(new ProductionRule
|
---|
261 | ((String) childSymbol,
|
---|
262 | new Object[] { getSymbol(executionVariant.task) }));
|
---|
263 | }
|
---|
264 | else {
|
---|
265 | // create iterative production rules
|
---|
266 | String iterationSymbol = childSymbol + "_it" + variantIndex;
|
---|
267 |
|
---|
268 | rules.add(new ProductionRule
|
---|
269 | (iterationSymbol,
|
---|
270 | new Object[] { iterationSymbol, executionVariant.task }));
|
---|
271 | rules.add(new ProductionRule(iterationSymbol,
|
---|
272 | new Object[] { executionVariant.task }));
|
---|
273 |
|
---|
274 | rules.add(new ProductionRule((String) childSymbol,
|
---|
275 | new Object[] { iterationSymbol }));
|
---|
276 | }
|
---|
277 |
|
---|
278 | variantIndex++;
|
---|
279 | }
|
---|
280 | }
|
---|
281 | else {
|
---|
282 | childSymbol = getSymbol(executionVariants.get(childIndex).get(0).task);
|
---|
283 | }
|
---|
284 |
|
---|
285 | if (isIteration(child)) {
|
---|
286 | // create iterative production rules
|
---|
287 | String iterationSymbol = sequence.getId() + "_it" + childIndex;
|
---|
288 |
|
---|
289 | rules.add(new ProductionRule(iterationSymbol,
|
---|
290 | new Object[] { iterationSymbol, childSymbol }));
|
---|
291 | rules.add(new ProductionRule(iterationSymbol, new Object[] { childSymbol }));
|
---|
292 |
|
---|
293 | childSymbol = iterationSymbol;
|
---|
294 | }
|
---|
295 |
|
---|
296 | rightHandSide.add(childSymbol);
|
---|
297 |
|
---|
298 | childIndex++;
|
---|
299 | }
|
---|
300 |
|
---|
301 | rules.add(new ProductionRule(Integer.toString(sequence.getId()),
|
---|
302 | rightHandSide.toArray()));
|
---|
303 |
|
---|
304 | }
|
---|
305 |
|
---|
306 | return rules;
|
---|
307 | }
|
---|
308 |
|
---|
309 | /**
|
---|
310 | *
|
---|
311 | */
|
---|
312 | private boolean isIteration(ITask child) {
|
---|
313 | if (child instanceof IIteration) {
|
---|
314 | return true;
|
---|
315 | }
|
---|
316 | else if (child instanceof IOptional) {
|
---|
317 | return isIteration(((IOptional) child).getMarkedTask());
|
---|
318 | }
|
---|
319 |
|
---|
320 | return false;
|
---|
321 | }
|
---|
322 |
|
---|
323 | /**
|
---|
324 | *
|
---|
325 | */
|
---|
326 | private Object getSymbol(ITask executionVariant) {
|
---|
327 | if (executionVariant instanceof IEventTask) {
|
---|
328 | return executionVariant;
|
---|
329 | }
|
---|
330 | else {
|
---|
331 | return Integer.toString(executionVariant.getId());
|
---|
332 | }
|
---|
333 | }
|
---|
334 |
|
---|
335 | /**
|
---|
336 | *
|
---|
337 | */
|
---|
338 | private ExecutionVariants getExecutionVariants(ITask task) {
|
---|
339 | if (task instanceof IOptional) {
|
---|
340 | ExecutionVariants result = getExecutionVariants(((IOptional) task).getMarkedTask());
|
---|
341 | result.setCanBeOptional();
|
---|
342 | return result;
|
---|
343 | }
|
---|
344 | else if (task instanceof ISelection) {
|
---|
345 | ExecutionVariants result = new ExecutionVariants();
|
---|
346 | for (ITask child : ((ISelection) task).getChildren()) {
|
---|
347 | result.addAll(getExecutionVariants(child));
|
---|
348 | }
|
---|
349 | return result;
|
---|
350 | }
|
---|
351 | else if (task instanceof IIteration) {
|
---|
352 | ExecutionVariants result = getExecutionVariants(((IIteration) task).getMarkedTask());
|
---|
353 | result.setCanBeIterated();
|
---|
354 | return result;
|
---|
355 | }
|
---|
356 | else {
|
---|
357 | ExecutionVariants result = new ExecutionVariants();
|
---|
358 | result.add(task);
|
---|
359 | return result;
|
---|
360 | }
|
---|
361 | }
|
---|
362 |
|
---|
363 | /**
|
---|
364 | *
|
---|
365 | */
|
---|
366 | private void addRulesIfNotThere(List<ProductionRule> rules,
|
---|
367 | List<ProductionRule> newRules)
|
---|
368 | {
|
---|
369 | for (ProductionRule newRule : newRules) {
|
---|
370 | boolean found = false;
|
---|
371 | for (ProductionRule candidate : rules) {
|
---|
372 | if (candidate.equals(newRule)) {
|
---|
373 | found = true;
|
---|
374 | break;
|
---|
375 | }
|
---|
376 | }
|
---|
377 |
|
---|
378 | if (!found) {
|
---|
379 | rules.add(newRule);
|
---|
380 | }
|
---|
381 | }
|
---|
382 | }
|
---|
383 |
|
---|
384 | /**
|
---|
385 | *
|
---|
386 | */
|
---|
387 | private List<ProductionRule> getRelevantRules(ITask task, List<ProductionRule> rules) {
|
---|
388 | List<ProductionRule> relevantRules = new LinkedList<>();
|
---|
389 | Set<String> handledNonTerminals = new HashSet<>();
|
---|
390 |
|
---|
391 | Stack<String> nonTerminals = new Stack<String>();
|
---|
392 | nonTerminals.push((String) getSymbol(task));
|
---|
393 |
|
---|
394 | // search for relevant rules that belong to the grammar initiated by the initial rule
|
---|
395 | do {
|
---|
396 | String nonTerminal = nonTerminals.pop();
|
---|
397 | handledNonTerminals.add(nonTerminal);
|
---|
398 |
|
---|
399 | for (ProductionRule candidate : rules) {
|
---|
400 | if (candidate.leftHandSide.equals(nonTerminal)) {
|
---|
401 | relevantRules.add(candidate);
|
---|
402 | for (int i = 0; i < candidate.rightHandSide.length; i++) {
|
---|
403 | if ((candidate.rightHandSide[i] instanceof String) &&
|
---|
404 | !handledNonTerminals.contains((String) candidate.rightHandSide[i]))
|
---|
405 | {
|
---|
406 | nonTerminals.push((String) candidate.rightHandSide[i]);
|
---|
407 | }
|
---|
408 | }
|
---|
409 | }
|
---|
410 | }
|
---|
411 | }
|
---|
412 | while (nonTerminals.size() > 0);
|
---|
413 |
|
---|
414 | return relevantRules;
|
---|
415 | }
|
---|
416 |
|
---|
417 | /**
|
---|
418 | *
|
---|
419 | */
|
---|
420 | private ParsingTable createParsingTable(ISequence task,
|
---|
421 | List<ProductionRule> rules)
|
---|
422 | {
|
---|
423 | ParsingTable table = new ParsingTable(task);
|
---|
424 |
|
---|
425 | List<ProductionRule> fullRuleSet = new LinkedList<>(rules);
|
---|
426 | ProductionRule initialRule = new ProductionRule("S'", new Object[] { getSymbol(task), EOF });
|
---|
427 | fullRuleSet.add(0, initialRule);
|
---|
428 | ProductionRulePosition initialPosition = new ProductionRulePosition(initialRule, 0);
|
---|
429 | State initialState = new State();
|
---|
430 | initialState.add(initialPosition);
|
---|
431 |
|
---|
432 | // create the state machine as typical for an LR(1) parser
|
---|
433 | List<State> states = new LinkedList<>();
|
---|
434 | states.add(closure(initialState, fullRuleSet));
|
---|
435 |
|
---|
436 | List<Edge> edges = new LinkedList<>();
|
---|
437 |
|
---|
438 | int noOfStates;
|
---|
439 | int noOfEdges;
|
---|
440 |
|
---|
441 | do {
|
---|
442 | noOfStates = states.size();
|
---|
443 | noOfEdges = edges.size();
|
---|
444 |
|
---|
445 | List<State> newStates = new LinkedList<State>();
|
---|
446 | List<Edge> newEdges = new LinkedList<Edge>();
|
---|
447 |
|
---|
448 | for (State state : states) {
|
---|
449 | for (ProductionRulePosition position : state) {
|
---|
450 | if (position.getNextSymbol() != null) {
|
---|
451 | State newState = gotoFunction(state, position.getNextSymbol(), fullRuleSet);
|
---|
452 | if (newState.size() > 0) {
|
---|
453 | State existing = null;
|
---|
454 |
|
---|
455 | for (State candidate : states) {
|
---|
456 | if (candidate.equals(newState)) {
|
---|
457 | existing = candidate;
|
---|
458 | break;
|
---|
459 | }
|
---|
460 | }
|
---|
461 |
|
---|
462 | if (existing == null) {
|
---|
463 | // check if the state is one of the new states
|
---|
464 | for (State candidate : newStates) {
|
---|
465 | if (candidate.equals(newState)) {
|
---|
466 | existing = candidate;
|
---|
467 | break;
|
---|
468 | }
|
---|
469 | }
|
---|
470 | }
|
---|
471 |
|
---|
472 | if (existing != null) {
|
---|
473 | newEdges.add(new Edge(state, existing, position.getNextSymbol()));
|
---|
474 | }
|
---|
475 | else {
|
---|
476 | newStates.add(newState);
|
---|
477 | newEdges.add(new Edge(state, newState, position.getNextSymbol()));
|
---|
478 | }
|
---|
479 | }
|
---|
480 | }
|
---|
481 | }
|
---|
482 | }
|
---|
483 |
|
---|
484 | addStatesIfNotContained(states, newStates);
|
---|
485 | addEdgesIfNotContained(edges, newEdges);
|
---|
486 | }
|
---|
487 | while ((noOfStates != states.size()) && (noOfEdges != edges.size()));
|
---|
488 |
|
---|
489 | /*System.out.println("\n\n\n\n");
|
---|
490 | new TaskTreeEncoder().encode(task, System.out);
|
---|
491 |
|
---|
492 | System.out.println("\n");
|
---|
493 | for (ProductionRule rule : fullRuleSet) {
|
---|
494 | System.out.println(rule);
|
---|
495 | }
|
---|
496 |
|
---|
497 | System.out.println("\n");
|
---|
498 | for (State state : states) {
|
---|
499 | System.out.println(state);
|
---|
500 | }
|
---|
501 |
|
---|
502 | System.out.println("\n");
|
---|
503 | for (Edge edge : edges) {
|
---|
504 | System.out.println
|
---|
505 | ("edge from " + edge.source.id + " to " + edge.dest.id + " on " + edge.symbol);
|
---|
506 | }*/
|
---|
507 |
|
---|
508 | // now create the table based on the states and edges
|
---|
509 | for (Edge edge : edges) {
|
---|
510 | if ((edge.symbol instanceof IEventTask) || (edge.symbol == EOF)) {
|
---|
511 | table.addShift(edge.dest, edge.source, edge.symbol);
|
---|
512 | }
|
---|
513 | else {
|
---|
514 | table.addGoto(edge.dest, edge.source, edge.symbol);
|
---|
515 | }
|
---|
516 | }
|
---|
517 |
|
---|
518 | for (State state : states) {
|
---|
519 | for (ProductionRulePosition position : state) {
|
---|
520 | if (position.getNextSymbol() == null) {
|
---|
521 | Set<Object> followSet =
|
---|
522 | getFollowSet(position.rule.leftHandSide, initialRule, fullRuleSet);
|
---|
523 |
|
---|
524 | for (Object symbol : followSet) {
|
---|
525 | table.addReduce(state, symbol, position.rule);
|
---|
526 | }
|
---|
527 | }
|
---|
528 | }
|
---|
529 | }
|
---|
530 |
|
---|
531 | /*System.out.println("\n");
|
---|
532 | System.out.println(task);
|
---|
533 |
|
---|
534 | System.out.println("\n");
|
---|
535 | System.out.println(table);
|
---|
536 |
|
---|
537 | List<List<IEventTask>> testinputs = new LinkedList<>();
|
---|
538 | for (ITaskInstance instance : task.getInstances()) {
|
---|
539 | final List<IEventTask> eventTasks = new ArrayList<>();
|
---|
540 |
|
---|
541 | instance.accept(new DefaultTaskInstanceTraversingVisitor() {
|
---|
542 | @Override
|
---|
543 | public void visit(IEventTaskInstance eventTaskInstance) {
|
---|
544 | eventTasks.add(eventTaskInstance.getEventTask());
|
---|
545 | }
|
---|
546 | });
|
---|
547 |
|
---|
548 | testinputs.add(eventTasks);
|
---|
549 | }
|
---|
550 |
|
---|
551 | List<ParsingTable> tables = new LinkedList<>();
|
---|
552 | tables.add(table);
|
---|
553 | parse(testinputs, tables);*/
|
---|
554 |
|
---|
555 | return table;
|
---|
556 | }
|
---|
557 |
|
---|
558 | /**
|
---|
559 | *
|
---|
560 | */
|
---|
561 | private Set<Object> getFollowSet(String leftHandSide,
|
---|
562 | ProductionRule initialRule,
|
---|
563 | List<ProductionRule> rules)
|
---|
564 | {
|
---|
565 | // search for all elements that may follow the given left hand side.
|
---|
566 | // consider also other non terminals whose production rules have a right hand side
|
---|
567 | // ending with the given left hand side
|
---|
568 |
|
---|
569 | Set<Object> result = new HashSet<>();
|
---|
570 | List<ProductionRulePosition> positions = new ArrayList<ProductionRulePosition>();
|
---|
571 | int index = 0;
|
---|
572 | positions.add
|
---|
573 | (new ProductionRulePosition(new ProductionRule(leftHandSide, new Object[] {}), 0));
|
---|
574 |
|
---|
575 | while (index < positions.size()) {
|
---|
576 | ProductionRulePosition productionRulePosition = positions.get(index++);
|
---|
577 | String nonTerminal = productionRulePosition.rule.leftHandSide;
|
---|
578 |
|
---|
579 | List<ProductionRulePosition> newPositions = new LinkedList<>();
|
---|
580 |
|
---|
581 | if (productionRulePosition.getNextSymbol() == null) {
|
---|
582 | // we are at the end of the production rule. Add further production rule positions
|
---|
583 | // for all parent production rules
|
---|
584 | for (ProductionRule candidate : rules) {
|
---|
585 | for (int i = 0; i < candidate.rightHandSide.length; i++) {
|
---|
586 | if (nonTerminal.equals(candidate.rightHandSide[i])) {
|
---|
587 | newPositions.add(new ProductionRulePosition(candidate, i + 1));
|
---|
588 | }
|
---|
589 | }
|
---|
590 | }
|
---|
591 | }
|
---|
592 | else {
|
---|
593 | // we are in the middle of a rule. If the next symbol is a terminal, add it to
|
---|
594 | // the resulting set. If not, add all rules of the respective non terminal with
|
---|
595 | // position 0 to the stack
|
---|
596 | if ((productionRulePosition.getNextSymbol() instanceof IEventTask) ||
|
---|
597 | (productionRulePosition.getNextSymbol() == EOF))
|
---|
598 | {
|
---|
599 | result.add(productionRulePosition.getNextSymbol());
|
---|
600 | }
|
---|
601 | else {
|
---|
602 | for (ProductionRule candidate : rules) {
|
---|
603 | if (candidate.leftHandSide.equals(productionRulePosition.getNextSymbol())) {
|
---|
604 | newPositions.add(new ProductionRulePosition(candidate, 0));
|
---|
605 | }
|
---|
606 | }
|
---|
607 | }
|
---|
608 | }
|
---|
609 |
|
---|
610 | for (ProductionRulePosition newPosition : newPositions) {
|
---|
611 | boolean found = false;
|
---|
612 |
|
---|
613 | for (ProductionRulePosition posCandidate : positions) {
|
---|
614 | if (posCandidate.equals(newPosition)) {
|
---|
615 | found = true;
|
---|
616 | break;
|
---|
617 | }
|
---|
618 | }
|
---|
619 |
|
---|
620 | if (!found) {
|
---|
621 | positions.add(newPosition);
|
---|
622 | }
|
---|
623 | }
|
---|
624 | }
|
---|
625 |
|
---|
626 | return result;
|
---|
627 | }
|
---|
628 |
|
---|
629 | /**
|
---|
630 | *
|
---|
631 | */
|
---|
632 | private State closure(State state, List<ProductionRule> rules) {
|
---|
633 | State closure = new State(state);
|
---|
634 | int statesize;
|
---|
635 |
|
---|
636 | do {
|
---|
637 | statesize = closure.size();
|
---|
638 |
|
---|
639 | List<ProductionRulePosition> newPositions = new LinkedList<>();
|
---|
640 |
|
---|
641 | for (ProductionRulePosition position : closure) {
|
---|
642 | Object nextSymbol = position.getNextSymbol();
|
---|
643 |
|
---|
644 | if (nextSymbol != null) {
|
---|
645 | for (ProductionRule candidate : rules) {
|
---|
646 | if (candidate.leftHandSide.equals(nextSymbol)) {
|
---|
647 | newPositions.add(new ProductionRulePosition(candidate, 0));
|
---|
648 | }
|
---|
649 | }
|
---|
650 | }
|
---|
651 | }
|
---|
652 |
|
---|
653 | for (ProductionRulePosition newPosition : newPositions) {
|
---|
654 | boolean alreadyContained = false;
|
---|
655 |
|
---|
656 | for (ProductionRulePosition existing : closure) {
|
---|
657 | if ((existing.rule == newPosition.rule) &&
|
---|
658 | (existing.position == newPosition.position))
|
---|
659 | {
|
---|
660 | alreadyContained = true;
|
---|
661 | break;
|
---|
662 | }
|
---|
663 | }
|
---|
664 |
|
---|
665 | if (!alreadyContained) {
|
---|
666 | closure.add(newPosition);
|
---|
667 | }
|
---|
668 | }
|
---|
669 | }
|
---|
670 | while (statesize != closure.size());
|
---|
671 |
|
---|
672 | return closure;
|
---|
673 | }
|
---|
674 |
|
---|
675 | /**
|
---|
676 | *
|
---|
677 | */
|
---|
678 | private State gotoFunction(State state, Object nextSymbol, List<ProductionRule> rules) {
|
---|
679 | State result = new State();
|
---|
680 |
|
---|
681 | for (ProductionRulePosition position : state) {
|
---|
682 | if (nextSymbol.equals(position.getNextSymbol())) {
|
---|
683 | ProductionRulePosition nextPosition = position.advance();
|
---|
684 | if (nextPosition != null) {
|
---|
685 | result.add(nextPosition);
|
---|
686 | }
|
---|
687 | }
|
---|
688 | }
|
---|
689 |
|
---|
690 | return closure(result, rules);
|
---|
691 | }
|
---|
692 |
|
---|
693 |
|
---|
694 | /**
|
---|
695 | *
|
---|
696 | */
|
---|
697 | private void addStatesIfNotContained(List<State> states, List<State> newStates) {
|
---|
698 |
|
---|
699 | for (State newState : newStates) {
|
---|
700 | boolean found = false;
|
---|
701 |
|
---|
702 | for (State candidate : states) {
|
---|
703 | if (candidate.equals(newState)) {
|
---|
704 | found = true;
|
---|
705 | break;
|
---|
706 | }
|
---|
707 | }
|
---|
708 |
|
---|
709 | if (!found) {
|
---|
710 | states.add(newState);
|
---|
711 | }
|
---|
712 | else {
|
---|
713 | throw new IllegalStateException
|
---|
714 | ("the algorithm should reuse existing states and not add them again");
|
---|
715 | }
|
---|
716 | }
|
---|
717 | }
|
---|
718 |
|
---|
719 | /**
|
---|
720 | *
|
---|
721 | */
|
---|
722 | private void addEdgesIfNotContained(List<Edge> edges, List<Edge> newEdges) {
|
---|
723 |
|
---|
724 | for (Edge newEdge : newEdges) {
|
---|
725 | boolean found = false;
|
---|
726 |
|
---|
727 | for (Edge candidate : edges) {
|
---|
728 | if (candidate.equals(newEdge)) {
|
---|
729 | found = true;
|
---|
730 | break;
|
---|
731 | }
|
---|
732 | }
|
---|
733 |
|
---|
734 | if (!found) {
|
---|
735 | edges.add(newEdge);
|
---|
736 | }
|
---|
737 | }
|
---|
738 | }
|
---|
739 |
|
---|
740 | /**
|
---|
741 | *
|
---|
742 | */
|
---|
743 | private int parse(List<List<IEventTask>> inputs,
|
---|
744 | List<ParsingTable> parsingTables,
|
---|
745 | Statistics statistics)
|
---|
746 | {
|
---|
747 | int sessionIndex = 0;
|
---|
748 | int allActions = 0;
|
---|
749 |
|
---|
750 | ParsingTableIndex tableIndex = new ParsingTableIndex(parsingTables, statistics);
|
---|
751 |
|
---|
752 | for (List<IEventTask> input : inputs) {
|
---|
753 | System.out.print("parsing session " + (sessionIndex + 1) + "/" + inputs.size() + ": ");
|
---|
754 |
|
---|
755 | List<Parser> currentParsers = new LinkedList<>();
|
---|
756 |
|
---|
757 | int index = 0;
|
---|
758 | for (IEventTask token : input) {
|
---|
759 | allActions++;
|
---|
760 | index++;
|
---|
761 |
|
---|
762 | for (ParsingTable table : tableIndex.getRelevantTables(token)) {
|
---|
763 | currentParsers.add(new Parser(table));
|
---|
764 | }
|
---|
765 |
|
---|
766 | //System.out.println(currentParsers.size() + " " + token);
|
---|
767 |
|
---|
768 | List<Parser> continuingParsers = new LinkedList<>();
|
---|
769 | for (Parser parser : currentParsers) {
|
---|
770 | Parser.Result result = parser.handleToken(token);
|
---|
771 |
|
---|
772 | if (result == Parser.Result.CONTINUE) {
|
---|
773 | Parser alternative = getParserInSameState(continuingParsers, parser);
|
---|
774 | if ((alternative == null) ||
|
---|
775 | (alternative.noOfParsedTokens < parser.noOfParsedTokens))
|
---|
776 | {
|
---|
777 | continuingParsers.add(parser);
|
---|
778 |
|
---|
779 | if (parser.checkSuccess()) {
|
---|
780 | //System.out.println("parser is continuing and also successing");
|
---|
781 | statistics.addCoveredActions
|
---|
782 | (parser.table.sequence, sessionIndex, input.size(),
|
---|
783 | index - parser.getNoOfParsedTokens(), index - 1);
|
---|
784 | }
|
---|
785 | }
|
---|
786 | }
|
---|
787 | else if (result == Parser.Result.SUCCESS) {
|
---|
788 | statistics.addCoveredActions
|
---|
789 | (parser.table.sequence, sessionIndex, input.size(),
|
---|
790 | index - parser.getNoOfParsedTokens(), index - 2);
|
---|
791 | }
|
---|
792 | }
|
---|
793 |
|
---|
794 | currentParsers = continuingParsers;
|
---|
795 | }
|
---|
796 |
|
---|
797 | for (Parser parser : currentParsers) {
|
---|
798 | if (parser.checkSuccess()) {
|
---|
799 | statistics.addCoveredActions
|
---|
800 | (parser.table.sequence, sessionIndex, input.size(),
|
---|
801 | index - parser.getNoOfParsedTokens(), index - 1);
|
---|
802 | }
|
---|
803 | }
|
---|
804 |
|
---|
805 | System.out.println
|
---|
806 | ("parsed " + statistics.getCoveredActions(sessionIndex) + " of " + input.size() +
|
---|
807 | " actions");
|
---|
808 |
|
---|
809 | sessionIndex++;
|
---|
810 | }
|
---|
811 |
|
---|
812 | System.out.println
|
---|
813 | ("parsed " + statistics.getRecalledActions() + " of " + allActions + " actions in " +
|
---|
814 | inputs.size() + " sessions (" + (100 * statistics.getRecalledActions() / allActions) +
|
---|
815 | "%)");
|
---|
816 |
|
---|
817 |
|
---|
818 | return statistics.getRecalledActions();
|
---|
819 | }
|
---|
820 |
|
---|
821 | /**
|
---|
822 | *
|
---|
823 | */
|
---|
824 | private Parser getParserInSameState(List<Parser> existingParsers, Parser parser) {
|
---|
825 | Stack<StackEntry> stack2 = parser.stack;
|
---|
826 |
|
---|
827 | PARSER:
|
---|
828 | for (Parser existing : existingParsers) {
|
---|
829 | if (existing.table != parser.table) {
|
---|
830 | continue;
|
---|
831 | }
|
---|
832 |
|
---|
833 | Stack<StackEntry> stack1 = existing.stack;
|
---|
834 |
|
---|
835 | if (stack1.size() == stack2.size()) {
|
---|
836 | Iterator<StackEntry> it1 = stack1.iterator();
|
---|
837 | Iterator<StackEntry> it2 = stack1.iterator();
|
---|
838 |
|
---|
839 | while (it1.hasNext()) {
|
---|
840 | StackEntry entry1 = it1.next();
|
---|
841 | StackEntry entry2 = it2.next();
|
---|
842 |
|
---|
843 | if (entry1.state != entry2.state) {
|
---|
844 | continue PARSER;
|
---|
845 | }
|
---|
846 |
|
---|
847 | if (entry1.symbol instanceof IEventTask) {
|
---|
848 | if (entry1.symbol != entry2.symbol) {
|
---|
849 | continue PARSER;
|
---|
850 | }
|
---|
851 | }
|
---|
852 | else if ((entry1.symbol != null) && (!entry1.symbol.equals(entry2.symbol))) {
|
---|
853 | continue PARSER;
|
---|
854 | }
|
---|
855 | else if (entry1.symbol != entry2.symbol) {
|
---|
856 | continue PARSER;
|
---|
857 | }
|
---|
858 | }
|
---|
859 |
|
---|
860 | // parsers are in same state
|
---|
861 | return existing;
|
---|
862 | }
|
---|
863 | }
|
---|
864 |
|
---|
865 | return null;
|
---|
866 | }
|
---|
867 |
|
---|
868 | /**
|
---|
869 | *
|
---|
870 | */
|
---|
871 | private static class Parser {
|
---|
872 |
|
---|
873 | /** */
|
---|
874 | private enum Result {
|
---|
875 | CONTINUE, FAIL, SUCCESS
|
---|
876 | }
|
---|
877 |
|
---|
878 | /** */
|
---|
879 | private ParsingTable table;
|
---|
880 |
|
---|
881 | /** */
|
---|
882 | private Stack<StackEntry> stack = new Stack<>();
|
---|
883 |
|
---|
884 | /** */
|
---|
885 | private int noOfParsedTokens = 0;
|
---|
886 |
|
---|
887 | /**
|
---|
888 | *
|
---|
889 | */
|
---|
890 | private Parser(ParsingTable table) {
|
---|
891 | this.table = table;
|
---|
892 | stack.push(new StackEntry(null, table.getInitialState()));
|
---|
893 | }
|
---|
894 |
|
---|
895 | /**
|
---|
896 | *
|
---|
897 | */
|
---|
898 | private int getNoOfParsedTokens() {
|
---|
899 | return noOfParsedTokens;
|
---|
900 | }
|
---|
901 |
|
---|
902 | /**
|
---|
903 | *
|
---|
904 | */
|
---|
905 | private boolean checkSuccess() {
|
---|
906 | // check the potential success of a copy of the stack to allow for parsing further
|
---|
907 | // tokens that are repetitions also allowed by the parser
|
---|
908 |
|
---|
909 | Stack<StackEntry> stackCopy = new Stack<>();
|
---|
910 |
|
---|
911 | for (StackEntry entry : stack) {
|
---|
912 | stackCopy.push(entry);
|
---|
913 | }
|
---|
914 |
|
---|
915 | Action action;
|
---|
916 |
|
---|
917 | do {
|
---|
918 | action = table.getAction(stackCopy.peek().state, EOF);
|
---|
919 |
|
---|
920 | if ((action != null) && (action.type == Action.Type.SHIFT)) {
|
---|
921 | return true;
|
---|
922 | }
|
---|
923 | else if ((action == null) || (action.type != Action.Type.REDUCE)) {
|
---|
924 | return false;
|
---|
925 | }
|
---|
926 |
|
---|
927 | ProductionRule rule = action.rule;
|
---|
928 | //System.out.println(" reducing " + rule);
|
---|
929 |
|
---|
930 | for (int i = rule.rightHandSide.length - 1; i >= 0; i--) {
|
---|
931 | /*StackEntry entry = */stackCopy.pop();
|
---|
932 | /*if (!entry.symbol.equals(rule.rightHandSide[i])) {
|
---|
933 | throw new RuntimeException("reduction seems to be wrong");
|
---|
934 | }*/
|
---|
935 | }
|
---|
936 |
|
---|
937 | Action gotoAct = table.getAction(stackCopy.peek().state, rule.leftHandSide);
|
---|
938 | State nextState = stackCopy.peek().state;
|
---|
939 | if (gotoAct != null) {
|
---|
940 | //System.out.println(" performing goto to " + gotoAct.dest.id);
|
---|
941 | nextState = gotoAct.dest;
|
---|
942 | }
|
---|
943 |
|
---|
944 | stackCopy.push(new StackEntry(rule.leftHandSide, nextState));
|
---|
945 | }
|
---|
946 | while (action != null);
|
---|
947 |
|
---|
948 | return true;
|
---|
949 | }
|
---|
950 |
|
---|
951 | /**
|
---|
952 | *
|
---|
953 | */
|
---|
954 | private Result handleToken(IEventTask token) {
|
---|
955 | noOfParsedTokens ++;
|
---|
956 |
|
---|
957 | Action action = table.getAction(stack.peek().state, token);
|
---|
958 |
|
---|
959 | if (action == null) {
|
---|
960 | if (checkSuccess()) {
|
---|
961 | return Result.SUCCESS;
|
---|
962 | }
|
---|
963 | else {
|
---|
964 | return Result.FAIL;
|
---|
965 | }
|
---|
966 | }
|
---|
967 |
|
---|
968 | /*System.out.println(" " + stack);
|
---|
969 | System.out.println(" " + token);
|
---|
970 | System.out.println
|
---|
971 | (" action for " + stack.peek().state.id + " on " + token + " is " + action);*/
|
---|
972 |
|
---|
973 | while (action.type == Action.Type.REDUCE) {
|
---|
974 | ProductionRule rule = action.rule;
|
---|
975 | //System.out.println(" reducing " + rule);
|
---|
976 |
|
---|
977 | for (int i = rule.rightHandSide.length - 1; i >= 0; i--) {
|
---|
978 | /*StackEntry entry = */stack.pop();
|
---|
979 | /*if (!entry.symbol.equals(rule.rightHandSide[i])) {
|
---|
980 | throw new RuntimeException("reduction seems to be wrong");
|
---|
981 | }*/
|
---|
982 | }
|
---|
983 |
|
---|
984 | Action gotoAct = table.getAction(stack.peek().state, rule.leftHandSide);
|
---|
985 | State nextState = stack.peek().state;
|
---|
986 | if (gotoAct != null) {
|
---|
987 | //System.out.println(" performing goto to " + gotoAct.dest.id);
|
---|
988 | nextState = gotoAct.dest;
|
---|
989 | }
|
---|
990 |
|
---|
991 | stack.push(new StackEntry(rule.leftHandSide, nextState));
|
---|
992 | action = table.getAction(stack.peek().state, token);
|
---|
993 |
|
---|
994 | if (action == null) {
|
---|
995 | if (checkSuccess()) {
|
---|
996 | return Result.SUCCESS;
|
---|
997 | }
|
---|
998 | else {
|
---|
999 | return Result.FAIL;
|
---|
1000 | }
|
---|
1001 | }
|
---|
1002 | }
|
---|
1003 |
|
---|
1004 | if (action.type == Action.Type.SHIFT) {
|
---|
1005 | //System.out.println(" shift to " + action.dest.id);
|
---|
1006 | stack.push(new StackEntry(token, action.dest));
|
---|
1007 | }
|
---|
1008 | else if (action.type == Action.Type.GOTO) {
|
---|
1009 | //System.out.println(" unexpected goto " + action.dest.id);
|
---|
1010 | stack.peek().state = action.dest;
|
---|
1011 | }
|
---|
1012 |
|
---|
1013 | return Result.CONTINUE;
|
---|
1014 | }
|
---|
1015 |
|
---|
1016 | }
|
---|
1017 |
|
---|
1018 | /**
|
---|
1019 | *
|
---|
1020 | */
|
---|
1021 | private static class ParsingTable {
|
---|
1022 |
|
---|
1023 | /** */
|
---|
1024 | private ISequence sequence;
|
---|
1025 |
|
---|
1026 | /** */
|
---|
1027 | private Map<State, List<ParsingTableEntry>> table = new IdentityHashMap<>();
|
---|
1028 |
|
---|
1029 | /**
|
---|
1030 | *
|
---|
1031 | */
|
---|
1032 | private ParsingTable(ISequence sequence) {
|
---|
1033 | this.sequence = sequence;
|
---|
1034 | }
|
---|
1035 |
|
---|
1036 | /**
|
---|
1037 | *
|
---|
1038 | */
|
---|
1039 | private void addShift(State dest, State source, Object symbol) {
|
---|
1040 | List<ParsingTableEntry> row = table.get(source);
|
---|
1041 |
|
---|
1042 | if (row == null) {
|
---|
1043 | row = new LinkedList<ParsingTableEntry>();
|
---|
1044 | table.put(source, row);
|
---|
1045 | }
|
---|
1046 |
|
---|
1047 | //System.out.println("adding shift " + dest.id + " for " + source.id + "," + symbol);
|
---|
1048 | row.add(new ParsingTableEntry(symbol, new Action(Action.Type.SHIFT, dest)));
|
---|
1049 | }
|
---|
1050 |
|
---|
1051 | /**
|
---|
1052 | *
|
---|
1053 | */
|
---|
1054 | private void addGoto(State dest, State source, Object symbol) {
|
---|
1055 | List<ParsingTableEntry> row = table.get(source);
|
---|
1056 |
|
---|
1057 | if (row == null) {
|
---|
1058 | row = new LinkedList<ParsingTableEntry>();
|
---|
1059 | table.put(source, row);
|
---|
1060 | }
|
---|
1061 |
|
---|
1062 | //System.out.println("adding goto " + dest.id + " for " + source.id + "," + symbol);
|
---|
1063 | row.add(new ParsingTableEntry(symbol, new Action(Action.Type.GOTO, dest)));
|
---|
1064 | }
|
---|
1065 |
|
---|
1066 | /**
|
---|
1067 | *
|
---|
1068 | */
|
---|
1069 | private void addReduce(State source, Object symbol, ProductionRule rule) {
|
---|
1070 | List<ParsingTableEntry> row = table.get(source);
|
---|
1071 |
|
---|
1072 | if (row == null) {
|
---|
1073 | row = new LinkedList<ParsingTableEntry>();
|
---|
1074 | table.put(source, row);
|
---|
1075 | }
|
---|
1076 |
|
---|
1077 | for (ParsingTableEntry entry : row) {
|
---|
1078 | if (entry.symbol.equals(symbol)) {
|
---|
1079 | System.out.println("conflict for " + source.id + " and terminal " + symbol +
|
---|
1080 | ": " + entry.action + " " + new Action(rule));
|
---|
1081 | throw new IllegalArgumentException("creating shift/reduce conflict");
|
---|
1082 | }
|
---|
1083 | }
|
---|
1084 |
|
---|
1085 | row.add(new ParsingTableEntry(symbol, new Action(rule)));
|
---|
1086 | }
|
---|
1087 |
|
---|
1088 | /**
|
---|
1089 | *
|
---|
1090 | */
|
---|
1091 | private State getInitialState() {
|
---|
1092 | for (State candidate : table.keySet()) {
|
---|
1093 | for (ProductionRulePosition position : candidate) {
|
---|
1094 | if ((position.position == 0) && (position.rule.leftHandSide.equals("S'"))) {
|
---|
1095 | return candidate;
|
---|
1096 | }
|
---|
1097 | }
|
---|
1098 |
|
---|
1099 | }
|
---|
1100 |
|
---|
1101 | return null;
|
---|
1102 | }
|
---|
1103 |
|
---|
1104 | /**
|
---|
1105 | *
|
---|
1106 | */
|
---|
1107 | private List<IEventTask> getInitialTokens() {
|
---|
1108 | State initialState = getInitialState();
|
---|
1109 |
|
---|
1110 | List<IEventTask> result = new LinkedList<>();
|
---|
1111 |
|
---|
1112 | for (ParsingTableEntry entry : table.get(initialState)) {
|
---|
1113 | if (entry.symbol instanceof IEventTask) {
|
---|
1114 | result.add((IEventTask) entry.symbol);
|
---|
1115 | }
|
---|
1116 | }
|
---|
1117 |
|
---|
1118 | return result;
|
---|
1119 | }
|
---|
1120 |
|
---|
1121 | /**
|
---|
1122 | *
|
---|
1123 | */
|
---|
1124 | private Action getAction(State state, Object symbol) {
|
---|
1125 | List<ParsingTableEntry> row = table.get(state);
|
---|
1126 |
|
---|
1127 | if (row != null) {
|
---|
1128 | if (symbol instanceof IEventTask) {
|
---|
1129 | for (ParsingTableEntry entry : row) {
|
---|
1130 | if (entry.symbol == symbol) {
|
---|
1131 | return entry.action;
|
---|
1132 | }
|
---|
1133 | }
|
---|
1134 | }
|
---|
1135 | else {
|
---|
1136 | for (ParsingTableEntry entry : row) {
|
---|
1137 | if (entry.symbol.equals(symbol)) {
|
---|
1138 | return entry.action;
|
---|
1139 | }
|
---|
1140 | }
|
---|
1141 | }
|
---|
1142 | }
|
---|
1143 |
|
---|
1144 | return null;
|
---|
1145 | }
|
---|
1146 |
|
---|
1147 | /* (non-Javadoc)
|
---|
1148 | * @see java.lang.Object#toString()
|
---|
1149 | */
|
---|
1150 | @Override
|
---|
1151 | public String toString() {
|
---|
1152 | Set<Object> eventTasks = new HashSet<>();
|
---|
1153 | eventTasks.add(EOF);
|
---|
1154 |
|
---|
1155 | Set<String> symbols = new HashSet<>();
|
---|
1156 | Set<State> states = new HashSet<>();
|
---|
1157 |
|
---|
1158 | for (Map.Entry<State, List<ParsingTableEntry>> entry : table.entrySet()) {
|
---|
1159 | for (ParsingTableEntry tableEntry : entry.getValue()) {
|
---|
1160 | if (tableEntry.symbol instanceof IEventTask) {
|
---|
1161 | eventTasks.add((IEventTask) tableEntry.symbol);
|
---|
1162 | }
|
---|
1163 | else if (tableEntry.symbol instanceof String) {
|
---|
1164 | symbols.add((String) tableEntry.symbol);
|
---|
1165 | }
|
---|
1166 | }
|
---|
1167 |
|
---|
1168 | states.add(entry.getKey());
|
---|
1169 | }
|
---|
1170 |
|
---|
1171 | StringBuffer result = new StringBuffer();
|
---|
1172 |
|
---|
1173 | result.append("\t|");
|
---|
1174 | for (Object task : eventTasks) {
|
---|
1175 | if (task instanceof IEventTask) {
|
---|
1176 | result.append(((IEventTask) task).getId());
|
---|
1177 | }
|
---|
1178 | else {
|
---|
1179 | result.append("EOF");
|
---|
1180 | }
|
---|
1181 | result.append("\t|");
|
---|
1182 | }
|
---|
1183 |
|
---|
1184 | for (String symbol : symbols) {
|
---|
1185 | result.append(symbol);
|
---|
1186 | result.append("\t|");
|
---|
1187 | }
|
---|
1188 |
|
---|
1189 | result.append('\n');
|
---|
1190 | result.append("--------------------------------------------------------------------\n");
|
---|
1191 |
|
---|
1192 | for (State state : states) {
|
---|
1193 | result.append(state.id);
|
---|
1194 |
|
---|
1195 | result.append("\t|");
|
---|
1196 |
|
---|
1197 | for (Object task : eventTasks) {
|
---|
1198 | Action act = null;
|
---|
1199 |
|
---|
1200 | if (table.containsKey(state)) {
|
---|
1201 | act = getAction(state, task);
|
---|
1202 | }
|
---|
1203 |
|
---|
1204 | if (act != null) {
|
---|
1205 | result.append(act);
|
---|
1206 | }
|
---|
1207 |
|
---|
1208 | result.append("\t|");
|
---|
1209 | }
|
---|
1210 |
|
---|
1211 | for (String symbol : symbols) {
|
---|
1212 | Action act = null;
|
---|
1213 |
|
---|
1214 | if (table.containsKey(state)) {
|
---|
1215 | act = getAction(state, symbol);
|
---|
1216 | }
|
---|
1217 |
|
---|
1218 | if (act != null) {
|
---|
1219 | result.append(act);
|
---|
1220 | }
|
---|
1221 |
|
---|
1222 | result.append("\t|");
|
---|
1223 | }
|
---|
1224 |
|
---|
1225 | result.append('\n');
|
---|
1226 | }
|
---|
1227 |
|
---|
1228 | return result.toString();
|
---|
1229 | }
|
---|
1230 |
|
---|
1231 |
|
---|
1232 | }
|
---|
1233 |
|
---|
1234 | /**
|
---|
1235 | *
|
---|
1236 | */
|
---|
1237 | private static class ParsingTableEntry {
|
---|
1238 |
|
---|
1239 | /** */
|
---|
1240 | private Object symbol;
|
---|
1241 |
|
---|
1242 | /** */
|
---|
1243 | private Action action;
|
---|
1244 |
|
---|
1245 | /**
|
---|
1246 | *
|
---|
1247 | */
|
---|
1248 | private ParsingTableEntry(Object symbol, Action action) {
|
---|
1249 | this.symbol = symbol;
|
---|
1250 | this.action = action;
|
---|
1251 | }
|
---|
1252 | }
|
---|
1253 |
|
---|
1254 | /**
|
---|
1255 | *
|
---|
1256 | */
|
---|
1257 | private static class Action {
|
---|
1258 |
|
---|
1259 | private enum Type {
|
---|
1260 | SHIFT, GOTO, REDUCE
|
---|
1261 | }
|
---|
1262 |
|
---|
1263 | /** */
|
---|
1264 | private Type type;
|
---|
1265 |
|
---|
1266 | /** */
|
---|
1267 | private State dest;
|
---|
1268 |
|
---|
1269 | /** */
|
---|
1270 | private ProductionRule rule;
|
---|
1271 |
|
---|
1272 | /**
|
---|
1273 | *
|
---|
1274 | */
|
---|
1275 | private Action(Type type, State dest) {
|
---|
1276 | this.type = type;
|
---|
1277 | this.dest = dest;
|
---|
1278 | this.rule = null;
|
---|
1279 | }
|
---|
1280 |
|
---|
1281 | /**
|
---|
1282 | *
|
---|
1283 | */
|
---|
1284 | private Action(ProductionRule rule) {
|
---|
1285 | this.type = Type.REDUCE;
|
---|
1286 | this.dest = null;
|
---|
1287 | this.rule = rule;
|
---|
1288 | }
|
---|
1289 |
|
---|
1290 | /* (non-Javadoc)
|
---|
1291 | * @see java.lang.Object#toString()
|
---|
1292 | */
|
---|
1293 | @Override
|
---|
1294 | public String toString() {
|
---|
1295 | switch (type) {
|
---|
1296 | case SHIFT: return "s" + dest.id;
|
---|
1297 | case GOTO: return "g" + dest.id;
|
---|
1298 | case REDUCE: return "r" + rule.id;
|
---|
1299 | }
|
---|
1300 |
|
---|
1301 | throw new IllegalStateException("action type must be one of shift, goto, and reduce");
|
---|
1302 | }
|
---|
1303 |
|
---|
1304 | }
|
---|
1305 |
|
---|
1306 | /**
|
---|
1307 | *
|
---|
1308 | */
|
---|
1309 | private static class ParsingTableIndex {
|
---|
1310 |
|
---|
1311 | /** */
|
---|
1312 | private Map<IEventTarget, List<ParsingTable>> index = new HashMap<>();
|
---|
1313 |
|
---|
1314 | /**
|
---|
1315 | *
|
---|
1316 | */
|
---|
1317 | private ParsingTableIndex(List<ParsingTable> allTables,
|
---|
1318 | Statistics statistics)
|
---|
1319 | {
|
---|
1320 | for (ParsingTable table : allTables) {
|
---|
1321 | statistics.addCheckedSequence(table.sequence);
|
---|
1322 |
|
---|
1323 | for (IEventTask firstToken : table.getInitialTokens()) {
|
---|
1324 | IEventTaskInstance exampleinstance =
|
---|
1325 | (IEventTaskInstance) firstToken.getInstances().iterator().next();
|
---|
1326 |
|
---|
1327 | List<ParsingTable> group = index.get(exampleinstance.getEvent().getTarget());
|
---|
1328 |
|
---|
1329 | if (group == null) {
|
---|
1330 | group = new LinkedList<>();
|
---|
1331 | index.put(exampleinstance.getEvent().getTarget(), group);
|
---|
1332 | }
|
---|
1333 |
|
---|
1334 | group.add(table);
|
---|
1335 | }
|
---|
1336 | }
|
---|
1337 | }
|
---|
1338 |
|
---|
1339 | /**
|
---|
1340 | *
|
---|
1341 | */
|
---|
1342 | private List<ParsingTable> getRelevantTables(IEventTask token) {
|
---|
1343 | IEventTaskInstance exampleinstance =
|
---|
1344 | (IEventTaskInstance) token.getInstances().iterator().next();
|
---|
1345 |
|
---|
1346 | List<ParsingTable> result = index.get(exampleinstance.getEvent().getTarget());
|
---|
1347 |
|
---|
1348 | if (result != null) {
|
---|
1349 | return result;
|
---|
1350 | }
|
---|
1351 | else {
|
---|
1352 | return new LinkedList<>();
|
---|
1353 | }
|
---|
1354 | }
|
---|
1355 |
|
---|
1356 | }
|
---|
1357 |
|
---|
1358 | /**
|
---|
1359 | *
|
---|
1360 | */
|
---|
1361 | private static class ProductionRule {
|
---|
1362 |
|
---|
1363 | /** */
|
---|
1364 | private String leftHandSide;
|
---|
1365 |
|
---|
1366 | /** */
|
---|
1367 | private Object[] rightHandSide;
|
---|
1368 |
|
---|
1369 | /** */
|
---|
1370 | private static int IDCOUNTER = 0;
|
---|
1371 |
|
---|
1372 | /** */
|
---|
1373 | private final int id = IDCOUNTER++;
|
---|
1374 |
|
---|
1375 | /**
|
---|
1376 | *
|
---|
1377 | */
|
---|
1378 | private ProductionRule(String leftHandSide, Object[] rightHandSide) {
|
---|
1379 | this.leftHandSide = leftHandSide;
|
---|
1380 | this.rightHandSide = rightHandSide;
|
---|
1381 | }
|
---|
1382 |
|
---|
1383 | /* (non-Javadoc)
|
---|
1384 | * @see java.lang.Object#toString()
|
---|
1385 | */
|
---|
1386 | @Override
|
---|
1387 | public String toString() {
|
---|
1388 | StringBuffer result = new StringBuffer();
|
---|
1389 | result.append(id);
|
---|
1390 | result.append(": ");
|
---|
1391 | result.append(leftHandSide);
|
---|
1392 | result.append(" ---> ");
|
---|
1393 |
|
---|
1394 | for (Object symbol : rightHandSide) {
|
---|
1395 | result.append(symbol);
|
---|
1396 | result.append(" ");
|
---|
1397 | }
|
---|
1398 |
|
---|
1399 | return result.toString();
|
---|
1400 | }
|
---|
1401 |
|
---|
1402 | /* (non-Javadoc)
|
---|
1403 | * @see java.lang.Object#equals(java.lang.Object)
|
---|
1404 | */
|
---|
1405 | @Override
|
---|
1406 | public boolean equals(Object obj) {
|
---|
1407 | if (obj == this) {
|
---|
1408 | return true;
|
---|
1409 | }
|
---|
1410 |
|
---|
1411 | if (!(obj instanceof ProductionRule)) {
|
---|
1412 | return false;
|
---|
1413 | }
|
---|
1414 |
|
---|
1415 | ProductionRule other = (ProductionRule) obj;
|
---|
1416 |
|
---|
1417 | if (!other.leftHandSide.equals(this.leftHandSide)) {
|
---|
1418 | return false;
|
---|
1419 | }
|
---|
1420 |
|
---|
1421 | if (other.rightHandSide.length != this.rightHandSide.length) {
|
---|
1422 | return false;
|
---|
1423 | }
|
---|
1424 |
|
---|
1425 | for (int i = 0; i < other.rightHandSide.length; i++) {
|
---|
1426 | if (!other.rightHandSide[i].equals(this.rightHandSide[i])) {
|
---|
1427 | return false;
|
---|
1428 | }
|
---|
1429 | }
|
---|
1430 |
|
---|
1431 | return true;
|
---|
1432 | }
|
---|
1433 |
|
---|
1434 | }
|
---|
1435 |
|
---|
1436 |
|
---|
1437 | /**
|
---|
1438 | *
|
---|
1439 | */
|
---|
1440 | private static class ProductionRulePosition {
|
---|
1441 |
|
---|
1442 | /** */
|
---|
1443 | private ProductionRule rule;
|
---|
1444 |
|
---|
1445 | /** */
|
---|
1446 | private int position;
|
---|
1447 |
|
---|
1448 | /**
|
---|
1449 | *
|
---|
1450 | */
|
---|
1451 | private ProductionRulePosition(ProductionRule rule, int position) {
|
---|
1452 | this.rule = rule;
|
---|
1453 | this.position = position;
|
---|
1454 | }
|
---|
1455 |
|
---|
1456 | /**
|
---|
1457 | *
|
---|
1458 | */
|
---|
1459 | private ProductionRulePosition advance() {
|
---|
1460 | if (position < rule.rightHandSide.length) {
|
---|
1461 | return new ProductionRulePosition(rule, position + 1);
|
---|
1462 | }
|
---|
1463 | else {
|
---|
1464 | return null;
|
---|
1465 | }
|
---|
1466 | }
|
---|
1467 |
|
---|
1468 | /**
|
---|
1469 | *
|
---|
1470 | */
|
---|
1471 | private Object getNextSymbol() {
|
---|
1472 | if (position < rule.rightHandSide.length) {
|
---|
1473 | return rule.rightHandSide[position];
|
---|
1474 | }
|
---|
1475 | else {
|
---|
1476 | return null;
|
---|
1477 | }
|
---|
1478 | }
|
---|
1479 |
|
---|
1480 | /* (non-Javadoc)
|
---|
1481 | * @see java.lang.Object#equals(java.lang.Object)
|
---|
1482 | */
|
---|
1483 | @Override
|
---|
1484 | public boolean equals(Object obj) {
|
---|
1485 | return (obj instanceof ProductionRulePosition) &&
|
---|
1486 | (this.rule.equals(((ProductionRulePosition) obj).rule)) &&
|
---|
1487 | (this.position == ((ProductionRulePosition) obj).position);
|
---|
1488 | }
|
---|
1489 |
|
---|
1490 | /* (non-Javadoc)
|
---|
1491 | * @see java.lang.Object#toString()
|
---|
1492 | */
|
---|
1493 | @Override
|
---|
1494 | public String toString() {
|
---|
1495 | return rule + " (position " + position + ")";
|
---|
1496 | }
|
---|
1497 | }
|
---|
1498 |
|
---|
1499 | /**
|
---|
1500 | *
|
---|
1501 | */
|
---|
1502 | private static class State extends ArrayList<ProductionRulePosition> {
|
---|
1503 |
|
---|
1504 | /** */
|
---|
1505 | private static final long serialVersionUID = 1L;
|
---|
1506 |
|
---|
1507 | /** */
|
---|
1508 | private static int IDCOUNTER = 0;
|
---|
1509 |
|
---|
1510 | /** */
|
---|
1511 | private final int id = IDCOUNTER++;
|
---|
1512 |
|
---|
1513 | /**
|
---|
1514 | *
|
---|
1515 | */
|
---|
1516 | private State() {
|
---|
1517 | super();
|
---|
1518 | }
|
---|
1519 |
|
---|
1520 | /**
|
---|
1521 | *
|
---|
1522 | */
|
---|
1523 | private State(Collection<? extends ProductionRulePosition> c) {
|
---|
1524 | super(c);
|
---|
1525 | }
|
---|
1526 |
|
---|
1527 | /* (non-Javadoc)
|
---|
1528 | * @see java.util.AbstractList#equals(java.lang.Object)
|
---|
1529 | */
|
---|
1530 | @Override
|
---|
1531 | public boolean equals(Object other) {
|
---|
1532 | if (!(other instanceof State)) {
|
---|
1533 | return false;
|
---|
1534 | }
|
---|
1535 |
|
---|
1536 | State otherState = (State) other;
|
---|
1537 |
|
---|
1538 | if (otherState.size() != this.size()) {
|
---|
1539 | return false;
|
---|
1540 | }
|
---|
1541 |
|
---|
1542 | for (ProductionRulePosition position : this) {
|
---|
1543 | boolean positionFound = false;
|
---|
1544 |
|
---|
1545 | for (ProductionRulePosition candidatePosition : otherState) {
|
---|
1546 | if (position.equals(candidatePosition)) {
|
---|
1547 | positionFound = true;
|
---|
1548 | break;
|
---|
1549 | }
|
---|
1550 | }
|
---|
1551 |
|
---|
1552 | if (!positionFound) {
|
---|
1553 | return false;
|
---|
1554 | }
|
---|
1555 | }
|
---|
1556 |
|
---|
1557 | return true;
|
---|
1558 | }
|
---|
1559 |
|
---|
1560 | /* (non-Javadoc)
|
---|
1561 | * @see java.util.AbstractCollection#toString()
|
---|
1562 | */
|
---|
1563 | @Override
|
---|
1564 | public String toString() {
|
---|
1565 | StringBuffer result = new StringBuffer();
|
---|
1566 | result.append("State ");
|
---|
1567 | result.append(id);
|
---|
1568 | result.append('\n');
|
---|
1569 |
|
---|
1570 | for (ProductionRulePosition pos : this) {
|
---|
1571 | result.append(" ");
|
---|
1572 | result.append(pos);
|
---|
1573 | result.append('\n');
|
---|
1574 | }
|
---|
1575 |
|
---|
1576 | return result.toString();
|
---|
1577 | }
|
---|
1578 |
|
---|
1579 | }
|
---|
1580 |
|
---|
1581 |
|
---|
1582 | /**
|
---|
1583 | *
|
---|
1584 | */
|
---|
1585 | private static class Edge {
|
---|
1586 |
|
---|
1587 | /** */
|
---|
1588 | private State source;
|
---|
1589 |
|
---|
1590 | /** */
|
---|
1591 | private State dest;
|
---|
1592 |
|
---|
1593 | /** */
|
---|
1594 | private Object symbol;
|
---|
1595 |
|
---|
1596 | /**
|
---|
1597 | *
|
---|
1598 | */
|
---|
1599 | private Edge(State source, State dest, Object symbol) {
|
---|
1600 | this.source = source;
|
---|
1601 | this.dest = dest;
|
---|
1602 | this.symbol = symbol;
|
---|
1603 | }
|
---|
1604 |
|
---|
1605 | /* (non-Javadoc)
|
---|
1606 | * @see java.lang.Object#equals(java.lang.Object)
|
---|
1607 | */
|
---|
1608 | @Override
|
---|
1609 | public boolean equals(Object obj) {
|
---|
1610 | if (this == obj) {
|
---|
1611 | return true;
|
---|
1612 | }
|
---|
1613 | else {
|
---|
1614 | return (obj instanceof Edge) && (((Edge) obj).source.equals(this.source)) &&
|
---|
1615 | (((Edge) obj).dest.equals(this.dest)) &&
|
---|
1616 | (((Edge) obj).symbol.equals(this.symbol));
|
---|
1617 | }
|
---|
1618 | }
|
---|
1619 | }
|
---|
1620 |
|
---|
1621 |
|
---|
1622 | /**
|
---|
1623 | *
|
---|
1624 | */
|
---|
1625 | private static class ExecutionVariants extends ArrayList<ExecutionVariant> {
|
---|
1626 |
|
---|
1627 | /** */
|
---|
1628 | private static final long serialVersionUID = 1L;
|
---|
1629 |
|
---|
1630 | /**
|
---|
1631 | *
|
---|
1632 | */
|
---|
1633 | private void setCanBeOptional() {
|
---|
1634 | for (ExecutionVariant variant : this) {
|
---|
1635 | variant.canBeOptional = true;
|
---|
1636 | }
|
---|
1637 | }
|
---|
1638 |
|
---|
1639 | /**
|
---|
1640 | *
|
---|
1641 | */
|
---|
1642 | private boolean canBeOptional() {
|
---|
1643 | for (ExecutionVariant variant : this) {
|
---|
1644 | if (variant.canBeOptional) {
|
---|
1645 | return true;
|
---|
1646 | }
|
---|
1647 | }
|
---|
1648 |
|
---|
1649 | return false;
|
---|
1650 | }
|
---|
1651 |
|
---|
1652 | /**
|
---|
1653 | *
|
---|
1654 | */
|
---|
1655 | private void add(ITask task) {
|
---|
1656 | super.add(new ExecutionVariant(task));
|
---|
1657 | }
|
---|
1658 |
|
---|
1659 | /**
|
---|
1660 | *
|
---|
1661 | */
|
---|
1662 | private void setCanBeIterated() {
|
---|
1663 | for (ExecutionVariant variant : this) {
|
---|
1664 | variant.canBeIterated = true;
|
---|
1665 | }
|
---|
1666 | }
|
---|
1667 |
|
---|
1668 | }
|
---|
1669 |
|
---|
1670 | /**
|
---|
1671 | *
|
---|
1672 | */
|
---|
1673 | private static class ExecutionVariant {
|
---|
1674 |
|
---|
1675 | /** */
|
---|
1676 | private ITask task;
|
---|
1677 |
|
---|
1678 | /** */
|
---|
1679 | private boolean canBeOptional = false;
|
---|
1680 |
|
---|
1681 | /** */
|
---|
1682 | private boolean canBeIterated = false;
|
---|
1683 |
|
---|
1684 | /**
|
---|
1685 | *
|
---|
1686 | */
|
---|
1687 | private ExecutionVariant(ITask task) {
|
---|
1688 | this.task = task;
|
---|
1689 | }
|
---|
1690 | }
|
---|
1691 |
|
---|
1692 | /**
|
---|
1693 | *
|
---|
1694 | */
|
---|
1695 | private static class StackEntry {
|
---|
1696 |
|
---|
1697 | /** */
|
---|
1698 | private Object symbol;
|
---|
1699 |
|
---|
1700 | /** */
|
---|
1701 | private State state;
|
---|
1702 |
|
---|
1703 | /**
|
---|
1704 | *
|
---|
1705 | */
|
---|
1706 | private StackEntry(Object symbol, State state) {
|
---|
1707 | super();
|
---|
1708 | this.symbol = symbol;
|
---|
1709 | this.state = state;
|
---|
1710 | }
|
---|
1711 |
|
---|
1712 | /* (non-Javadoc)
|
---|
1713 | * @see java.lang.Object#toString()
|
---|
1714 | */
|
---|
1715 | @Override
|
---|
1716 | public String toString() {
|
---|
1717 | return "(" + symbol + "," + state.id + ")";
|
---|
1718 | }
|
---|
1719 | }
|
---|
1720 |
|
---|
1721 | /**
|
---|
1722 | *
|
---|
1723 | */
|
---|
1724 | private static class Statistics {
|
---|
1725 |
|
---|
1726 | /** */
|
---|
1727 | private ITaskModel comparedModel;
|
---|
1728 |
|
---|
1729 | /** */
|
---|
1730 | private ITaskModel comparedWithModel;
|
---|
1731 |
|
---|
1732 | /** */
|
---|
1733 | private Map<Integer, boolean[]> sessionCoverage = new HashMap<>();
|
---|
1734 |
|
---|
1735 | /** */
|
---|
1736 | private Map<ISequence, Map<Integer, boolean[]>> sequenceCoverage = new HashMap<>();
|
---|
1737 |
|
---|
1738 | /** */
|
---|
1739 | private int allEventsOfComparedModel;
|
---|
1740 |
|
---|
1741 | /** */
|
---|
1742 | private int allSequencesOfComparedModel;
|
---|
1743 |
|
---|
1744 | /** */
|
---|
1745 | private int eventsCoveredBySequencesOfComparedModel;
|
---|
1746 |
|
---|
1747 | /** */
|
---|
1748 | private int allEventsOfComparedWithModel;
|
---|
1749 |
|
---|
1750 | /** */
|
---|
1751 | private int allSequencesOfComparedWithModel;
|
---|
1752 |
|
---|
1753 | /** */
|
---|
1754 | private int eventsCoveredBySequencesOfComparedWithModel;
|
---|
1755 |
|
---|
1756 | /**
|
---|
1757 | *
|
---|
1758 | */
|
---|
1759 | private Statistics(ITaskModel comparedModel, ITaskModel comparedWithModel) {
|
---|
1760 | super();
|
---|
1761 | this.comparedModel = comparedModel;
|
---|
1762 | this.comparedWithModel = comparedWithModel;
|
---|
1763 |
|
---|
1764 | this.allEventsOfComparedModel = getAllEvents(comparedModel);
|
---|
1765 | Set<ISequence> sequences = getSequences(comparedModel);
|
---|
1766 | this.allSequencesOfComparedModel = sequences.size();
|
---|
1767 | this.eventsCoveredBySequencesOfComparedModel =
|
---|
1768 | TaskTreeUtils.getNoOfEventsCoveredBySequences(sequences);
|
---|
1769 |
|
---|
1770 | this.allEventsOfComparedWithModel = getAllEvents(comparedWithModel);
|
---|
1771 | sequences = getSequences(comparedWithModel);
|
---|
1772 | this.allSequencesOfComparedWithModel = sequences.size();
|
---|
1773 | this.eventsCoveredBySequencesOfComparedWithModel =
|
---|
1774 | TaskTreeUtils.getNoOfEventsCoveredBySequences(sequences);
|
---|
1775 | }
|
---|
1776 |
|
---|
1777 | /**
|
---|
1778 | *
|
---|
1779 | */
|
---|
1780 | private Set<ISequence> getSequences(ITaskModel model) {
|
---|
1781 | Set<ISequence> result = new HashSet<>();
|
---|
1782 |
|
---|
1783 | for (ITask candidate : model.getTasks()) {
|
---|
1784 | if (candidate instanceof ISequence) {
|
---|
1785 | result.add((ISequence) candidate);
|
---|
1786 | }
|
---|
1787 | }
|
---|
1788 |
|
---|
1789 | return result;
|
---|
1790 | }
|
---|
1791 |
|
---|
1792 | /**
|
---|
1793 | *
|
---|
1794 | */
|
---|
1795 | private int getAllEvents(ITaskModel model) {
|
---|
1796 | int allEvents = 0;
|
---|
1797 |
|
---|
1798 | for (ITask task : model.getTasks()) {
|
---|
1799 | if (task instanceof IEventTask) {
|
---|
1800 | allEvents += task.getInstances().size();
|
---|
1801 | }
|
---|
1802 | }
|
---|
1803 |
|
---|
1804 | return allEvents;
|
---|
1805 | }
|
---|
1806 |
|
---|
1807 | /**
|
---|
1808 | *
|
---|
1809 | */
|
---|
1810 | private int getCoveredActions(int sessionIndex) {
|
---|
1811 | boolean[] coveredActions = sessionCoverage.get(sessionIndex);
|
---|
1812 |
|
---|
1813 | if (coveredActions == null) {
|
---|
1814 | return 0;
|
---|
1815 | }
|
---|
1816 | else {
|
---|
1817 | int counter = 0;
|
---|
1818 |
|
---|
1819 | for (int i = 0; i < coveredActions.length; i++) {
|
---|
1820 | if (coveredActions[i]) {
|
---|
1821 | counter++;
|
---|
1822 | }
|
---|
1823 | }
|
---|
1824 |
|
---|
1825 | return counter;
|
---|
1826 | }
|
---|
1827 | }
|
---|
1828 |
|
---|
1829 | /**
|
---|
1830 | *
|
---|
1831 | */
|
---|
1832 | private int getRecalledActions() {
|
---|
1833 | int overallCoverage = 0;
|
---|
1834 |
|
---|
1835 | for (boolean[] coveredActions : sessionCoverage.values()) {
|
---|
1836 | for (int i = 0; i < coveredActions.length; i++) {
|
---|
1837 | if (coveredActions[i]) {
|
---|
1838 | overallCoverage++;
|
---|
1839 | }
|
---|
1840 | }
|
---|
1841 | }
|
---|
1842 |
|
---|
1843 | return overallCoverage;
|
---|
1844 | }
|
---|
1845 |
|
---|
1846 | /**
|
---|
1847 | *
|
---|
1848 | */
|
---|
1849 | private int getRecalledActionsOf(Set<ISequence> sequences) {
|
---|
1850 | Map<Integer, boolean[]> combinedCoveredSessions = new HashMap<>();
|
---|
1851 |
|
---|
1852 | for (ISequence sequence : sequences) {
|
---|
1853 | Map<Integer, boolean[]> coveredSessions = sequenceCoverage.get(sequence);
|
---|
1854 |
|
---|
1855 | if (coveredSessions != null) {
|
---|
1856 | for (Map.Entry<Integer, boolean[]> entry : coveredSessions.entrySet()) {
|
---|
1857 | boolean[] combinedSession = combinedCoveredSessions.get(entry.getKey());
|
---|
1858 |
|
---|
1859 | if (combinedSession == null) {
|
---|
1860 | combinedSession = new boolean[entry.getValue().length];
|
---|
1861 | combinedCoveredSessions.put(entry.getKey(), combinedSession);
|
---|
1862 | }
|
---|
1863 |
|
---|
1864 | for (int i = 0; i < combinedSession.length; i++) {
|
---|
1865 | if (entry.getValue()[i]) {
|
---|
1866 | combinedSession[i] = true;
|
---|
1867 | }
|
---|
1868 | }
|
---|
1869 | }
|
---|
1870 | }
|
---|
1871 | }
|
---|
1872 |
|
---|
1873 | int overallCoverage = 0;
|
---|
1874 |
|
---|
1875 | for (boolean[] coveredActions : combinedCoveredSessions.values()) {
|
---|
1876 | for (int i = 0; i < coveredActions.length; i++) {
|
---|
1877 | if (coveredActions[i]) {
|
---|
1878 | overallCoverage++;
|
---|
1879 | }
|
---|
1880 | }
|
---|
1881 | }
|
---|
1882 |
|
---|
1883 | return overallCoverage;
|
---|
1884 | }
|
---|
1885 |
|
---|
1886 | /**
|
---|
1887 | *
|
---|
1888 | */
|
---|
1889 | private void addCheckedSequence(ISequence coveringSequence) {
|
---|
1890 | Map<Integer, boolean[]> coveredSessions = sequenceCoverage.get(coveringSequence);
|
---|
1891 |
|
---|
1892 | if (coveredSessions == null) {
|
---|
1893 | coveredSessions = new HashMap<>();
|
---|
1894 | sequenceCoverage.put(coveringSequence, coveredSessions);
|
---|
1895 | }
|
---|
1896 | }
|
---|
1897 |
|
---|
1898 | /**
|
---|
1899 | *
|
---|
1900 | */
|
---|
1901 | private void addCoveredActions(ISequence coveringSequence,
|
---|
1902 | int sessionIndex,
|
---|
1903 | int sessionSize,
|
---|
1904 | int indexFirstAction,
|
---|
1905 | int indexLastAction)
|
---|
1906 | {
|
---|
1907 | boolean[] coveredActions = sessionCoverage.get(sessionIndex);
|
---|
1908 |
|
---|
1909 | if (coveredActions == null) {
|
---|
1910 | coveredActions = new boolean[sessionSize];
|
---|
1911 | sessionCoverage.put(sessionIndex, coveredActions);
|
---|
1912 | }
|
---|
1913 |
|
---|
1914 | for (int i = indexFirstAction; i <= indexLastAction; i++) {
|
---|
1915 | coveredActions[i] = true;
|
---|
1916 | }
|
---|
1917 |
|
---|
1918 | Map<Integer, boolean[]> coveredSessions = sequenceCoverage.get(coveringSequence);
|
---|
1919 |
|
---|
1920 | if (coveredSessions == null) {
|
---|
1921 | coveredSessions = new HashMap<>();
|
---|
1922 | sequenceCoverage.put(coveringSequence, coveredSessions);
|
---|
1923 | }
|
---|
1924 |
|
---|
1925 | coveredActions = coveredSessions.get(sessionIndex);
|
---|
1926 |
|
---|
1927 | if (coveredActions == null) {
|
---|
1928 | coveredActions = new boolean[sessionSize];
|
---|
1929 | coveredSessions.put(sessionIndex, coveredActions);
|
---|
1930 | }
|
---|
1931 |
|
---|
1932 | for (int i = indexFirstAction; i <= indexLastAction; i++) {
|
---|
1933 | coveredActions[i] = true;
|
---|
1934 | }
|
---|
1935 | }
|
---|
1936 |
|
---|
1937 | /**
|
---|
1938 | *
|
---|
1939 | */
|
---|
1940 | private void dump(PrintStream out) {
|
---|
1941 | Set<ISequence> mostProminentSequences =
|
---|
1942 | TaskTreeUtils.getMostProminentSequences(comparedModel, sequenceCoverage.keySet());
|
---|
1943 |
|
---|
1944 | int eventsCoveredByAllSequences =
|
---|
1945 | TaskTreeUtils.getNoOfEventsCoveredBySequences(sequenceCoverage.keySet());
|
---|
1946 |
|
---|
1947 | int eventsCoveredByMostProminent =
|
---|
1948 | TaskTreeUtils.getNoOfEventsCoveredBySequences(mostProminentSequences);
|
---|
1949 |
|
---|
1950 | int recalledActions = getRecalledActions();
|
---|
1951 | int recalledActionsMostProminent = getRecalledActionsOf(mostProminentSequences);
|
---|
1952 |
|
---|
1953 | out.println("\nComparison Statistics");
|
---|
1954 | out.println("=======================================================================");
|
---|
1955 | out.println("compared model: " + comparedModel);
|
---|
1956 | out.println(" all actions in sessions: " +
|
---|
1957 | allEventsOfComparedModel);
|
---|
1958 | out.println(" all sequences of model: " +
|
---|
1959 | allSequencesOfComparedModel);
|
---|
1960 | out.println(" checked sequences of model: " +
|
---|
1961 | formatPerc(sequenceCoverage.keySet().size(), allSequencesOfComparedModel));
|
---|
1962 | out.println(" most prominent checked sequences of model: " +
|
---|
1963 | mostProminentSequences.size());
|
---|
1964 | out.println(" actions covered by all sequences: " +
|
---|
1965 | formatPerc(eventsCoveredBySequencesOfComparedModel, allEventsOfComparedModel));
|
---|
1966 | out.println(" actions covered by checked sequences: " +
|
---|
1967 | formatPerc(eventsCoveredByAllSequences, allEventsOfComparedModel));
|
---|
1968 | out.println("actions covered by most prominent checked sequences: " +
|
---|
1969 | formatPerc(eventsCoveredByMostProminent, allEventsOfComparedModel));
|
---|
1970 | out.println();
|
---|
1971 | out.println("compared with: " + comparedWithModel);
|
---|
1972 | out.println(" all actions in sessions: " +
|
---|
1973 | allEventsOfComparedWithModel);
|
---|
1974 | out.println(" all sequences of model: " +
|
---|
1975 | allSequencesOfComparedWithModel);
|
---|
1976 | out.println(" actions covered by all sequences: " +
|
---|
1977 | formatPerc(eventsCoveredBySequencesOfComparedWithModel,
|
---|
1978 | allEventsOfComparedWithModel));
|
---|
1979 | out.println();
|
---|
1980 | out.println(" actions covered by checked sequences: " +
|
---|
1981 | formatPerc(recalledActions, allEventsOfComparedWithModel));
|
---|
1982 |
|
---|
1983 | out.println(" actions covered by most prominent sequences: " +
|
---|
1984 | formatPerc(recalledActionsMostProminent, allEventsOfComparedWithModel));
|
---|
1985 | out.println();
|
---|
1986 |
|
---|
1987 | out.print("CSV: ");
|
---|
1988 | out.print(allEventsOfComparedModel);
|
---|
1989 | out.print(";");
|
---|
1990 | out.print(allSequencesOfComparedModel);
|
---|
1991 | out.print(";");
|
---|
1992 | out.print(sequenceCoverage.keySet().size());
|
---|
1993 | out.print(";");
|
---|
1994 | out.print((double) sequenceCoverage.keySet().size() / allSequencesOfComparedModel);
|
---|
1995 | out.print(";");
|
---|
1996 | out.print(mostProminentSequences.size());
|
---|
1997 | out.print(";");
|
---|
1998 | out.print(eventsCoveredBySequencesOfComparedModel);
|
---|
1999 | out.print(";");
|
---|
2000 | out.print((double) eventsCoveredBySequencesOfComparedModel / allEventsOfComparedModel);
|
---|
2001 | out.print(";");
|
---|
2002 | out.print(eventsCoveredByAllSequences);
|
---|
2003 | out.print(";");
|
---|
2004 | out.print((double) eventsCoveredByAllSequences / allEventsOfComparedModel);
|
---|
2005 | out.print(";");
|
---|
2006 | out.print(eventsCoveredByMostProminent);
|
---|
2007 | out.print(";");
|
---|
2008 | out.print((double) eventsCoveredByMostProminent / allEventsOfComparedModel);
|
---|
2009 | out.print(";");
|
---|
2010 | out.print(allEventsOfComparedWithModel);
|
---|
2011 | out.print(";");
|
---|
2012 | out.print(allSequencesOfComparedWithModel);
|
---|
2013 | out.print(";");
|
---|
2014 | out.print(eventsCoveredBySequencesOfComparedWithModel);
|
---|
2015 | out.print(";");
|
---|
2016 | out.print((double) eventsCoveredBySequencesOfComparedWithModel / allEventsOfComparedWithModel);
|
---|
2017 | out.print(";");
|
---|
2018 | out.print(recalledActions);
|
---|
2019 | out.print(";");
|
---|
2020 | out.print((double) recalledActions / allEventsOfComparedWithModel);
|
---|
2021 | out.print(";");
|
---|
2022 | out.print(recalledActionsMostProminent);
|
---|
2023 | out.print(";");
|
---|
2024 | out.print((double) recalledActionsMostProminent / allEventsOfComparedWithModel);
|
---|
2025 | out.println();
|
---|
2026 | out.println();
|
---|
2027 |
|
---|
2028 |
|
---|
2029 | /*for (final ISequence sequence : sequenceCoverage.keySet()) {
|
---|
2030 | Set<ISequence> tmp = new HashSet<>();
|
---|
2031 | tmp.add(sequence);
|
---|
2032 | if (comparedModel.getTaskInfo(sequence).getMeasureValue(TaskMetric.EVENT_COVERAGE) >= getRecalledActionsOf(tmp)) {
|
---|
2033 | continue;
|
---|
2034 | }
|
---|
2035 |
|
---|
2036 | System.out.println();
|
---|
2037 | System.out.println(comparedModel.getTaskInfo(sequence).getMeasureValue(TaskMetric.EVENT_COVERAGE) +
|
---|
2038 | " " + getRecalledActionsOf(tmp));
|
---|
2039 | new TaskTreeEncoder().encode(sequence, System.out);
|
---|
2040 |
|
---|
2041 | final List<IEventTaskInstance> eventList = new LinkedList<>();
|
---|
2042 | int sessionIndex = 0;
|
---|
2043 | for (IUserSession session : comparedModel.getUserSessions()) {
|
---|
2044 | sessionIndex++;
|
---|
2045 |
|
---|
2046 | System.out.println("\ncoverage in session " + sessionIndex + " (" +
|
---|
2047 | session.size() + ")");
|
---|
2048 |
|
---|
2049 | //new TaskTreeEncoder().encode(session, System.out);
|
---|
2050 |
|
---|
2051 | final int[] index = new int[1];
|
---|
2052 | index[0] = 0;
|
---|
2053 |
|
---|
2054 | for (ITaskInstance instance : session) {
|
---|
2055 | instance.accept(new DefaultTaskInstanceTraversingVisitor() {
|
---|
2056 | @Override
|
---|
2057 | public void visit(IEventTaskInstance eventTaskInstance) {
|
---|
2058 | eventList.add(eventTaskInstance);
|
---|
2059 | }
|
---|
2060 |
|
---|
2061 | @Override
|
---|
2062 | public void visit(ISequenceInstance sequenceInstance) {
|
---|
2063 | if (sequenceInstance.getTask() == sequence) {
|
---|
2064 | eventList.clear();
|
---|
2065 | }
|
---|
2066 | super.visit(sequenceInstance);
|
---|
2067 | if (sequenceInstance.getTask() == sequence) {
|
---|
2068 | System.out.println("source: " + index[0] + " " + eventList);
|
---|
2069 | }
|
---|
2070 | }
|
---|
2071 | });
|
---|
2072 | index[0]++;
|
---|
2073 | }
|
---|
2074 |
|
---|
2075 | System.out.println("dest session " + comparedWithModel.getUserSessions().get(sessionIndex - 1).size());
|
---|
2076 | eventList.clear();
|
---|
2077 | final boolean[] covered = sequenceCoverage.get(sequence).get(sessionIndex - 1);
|
---|
2078 |
|
---|
2079 | if (covered == null) {
|
---|
2080 | System.out.println("no dest");
|
---|
2081 | continue;
|
---|
2082 | }
|
---|
2083 |
|
---|
2084 | final int[] counter = new int[1];
|
---|
2085 | index[0] = 0;
|
---|
2086 |
|
---|
2087 | for (ITaskInstance instance : comparedWithModel.getUserSessions().get(sessionIndex - 1)) {
|
---|
2088 | instance.accept(new DefaultTaskInstanceTraversingVisitor() {
|
---|
2089 | @Override
|
---|
2090 | public void visit(IEventTaskInstance eventTaskInstance) {
|
---|
2091 | if (covered[counter[0]]) {
|
---|
2092 | eventList.add(eventTaskInstance);
|
---|
2093 | }
|
---|
2094 | else {
|
---|
2095 | if (eventList.size() > 0) {
|
---|
2096 | System.out.println("dest: " + index[0] + " " + eventList);
|
---|
2097 | }
|
---|
2098 | eventList.clear();
|
---|
2099 | }
|
---|
2100 |
|
---|
2101 | counter[0]++;
|
---|
2102 | }
|
---|
2103 | });
|
---|
2104 |
|
---|
2105 | index[0]++;
|
---|
2106 | }
|
---|
2107 |
|
---|
2108 | if (eventList.size() > 0) {
|
---|
2109 | System.out.println("dest: " + eventList);
|
---|
2110 | }
|
---|
2111 | }
|
---|
2112 | }*/
|
---|
2113 | }
|
---|
2114 |
|
---|
2115 | /**
|
---|
2116 | *
|
---|
2117 | */
|
---|
2118 | private String formatPerc(int part, int of) {
|
---|
2119 | return (100 * part / of) + "% (" + part + "/" + of + ")";
|
---|
2120 | }
|
---|
2121 | }
|
---|
2122 | }
|
---|