// Copyright 2012 Georg-August-Universität Göttingen, Germany
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package de.ugoe.cs.autoquest.commands.usability;
import java.io.PrintStream;
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.HashSet;
import java.util.IdentityHashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.Stack;
import de.ugoe.cs.autoquest.CommandHelpers;
import de.ugoe.cs.autoquest.eventcore.IEventTarget;
import de.ugoe.cs.autoquest.tasktrees.taskequality.TaskEquality;
import de.ugoe.cs.autoquest.tasktrees.temporalrelation.TaskHandlingStrategy;
import de.ugoe.cs.autoquest.tasktrees.treeifc.DefaultTaskInstanceTraversingVisitor;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTask;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IEventTaskInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IIteration;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IOptional;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISelection;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ISequence;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITask;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskInstance;
import de.ugoe.cs.autoquest.tasktrees.treeifc.ITaskModel;
import de.ugoe.cs.autoquest.tasktrees.treeifc.IUserSession;
import de.ugoe.cs.autoquest.tasktrees.treeifc.TaskTreeUtils;
import de.ugoe.cs.autoquest.usageprofiles.SymbolMap;
import de.ugoe.cs.util.console.Command;
import de.ugoe.cs.util.console.Console;
import de.ugoe.cs.util.console.GlobalDataContainer;
/**
*
* compares a set of task models with each other and drops their similarity as results
*
*
* @author Patrick Harms
* @version 1.0
*/
public class CMDgetTaskModelCrossCoverage implements Command {
/** */
private static Object EOF = new Object();
/*
* (non-Javadoc)
*
* @see de.ugoe.cs.util.console.Command#help()
*/
@Override
public String help() {
return "getTaskModelCrossCoverage ...";
}
/*
* (non-Javadoc)
*
* @see de.ugoe.cs.util.console.Command#run(java.util.List)
*/
@Override
public void run(List parameters) {
List inputTaskTreeNames = new LinkedList<>();
try {
for (Object param : parameters) {
inputTaskTreeNames.add((String) param);
}
}
catch (Exception e) {
throw new IllegalArgumentException("must provide valid input task tree names");
}
Map>> inputTaskModels = new IdentityHashMap<>();
ITaskModel firstModel = null;
final SymbolMap eventTasksOfFirstModel =
new TaskHandlingStrategy(TaskEquality.SEMANTICALLY_EQUAL).createSymbolMap();
for (String inputTaskTreeName : inputTaskTreeNames) {
Object dataObject = GlobalDataContainer.getInstance().getData(inputTaskTreeName);
if (dataObject == null) {
CommandHelpers.objectNotFoundMessage(inputTaskTreeName);
continue;
}
if (!(dataObject instanceof ITaskModel)) {
CommandHelpers.objectNotType(inputTaskTreeName, "ITaskModel");
continue;
}
System.out.println("preparing sessions to check for " + dataObject);
List> sessionsToCheck = new LinkedList<>();
final Map identityMap = new IdentityHashMap<>();
for (IUserSession session : ((ITaskModel) dataObject).getUserSessions()) {
final List eventTasks = new ArrayList<>();
for (ITaskInstance instance : session) {
instance.accept(new DefaultTaskInstanceTraversingVisitor() {
@Override
public void visit(IEventTaskInstance eventTaskInstance) {
IEventTask eventTask = eventTaskInstance.getEventTask();
IEventTask replacement = identityMap.get(eventTask);
if (replacement == null) {
replacement = eventTasksOfFirstModel.getValue(eventTask);
if (replacement == null) {
replacement = eventTaskInstance.getEventTask();
eventTasksOfFirstModel.addSymbol(replacement, replacement);
}
identityMap.put(eventTask, replacement);
}
eventTasks.add(replacement);
}
});
}
sessionsToCheck.add(eventTasks);
}
inputTaskModels.put((ITaskModel) dataObject, sessionsToCheck);
if (firstModel == null) {
firstModel = (ITaskModel) dataObject;
}
}
getTaskModelCrossCoverage(firstModel, inputTaskModels);
}
/**
*
*/
private void getTaskModelCrossCoverage(ITaskModel modelToCompare,
Map>> sessionsToCheck)
{
System.out.println("creating parsing tables for " + modelToCompare);
List parsingTables = getParsingTables(modelToCompare);
for (Map.Entry>> entry : sessionsToCheck.entrySet()) {
if (entry.getKey() != modelToCompare) {
System.out.println("performing parsing against " + entry.getKey());
Statistics statistics = new Statistics(modelToCompare, entry.getKey());
parse(entry.getValue(), parsingTables, statistics);
statistics.dump(System.out);
}
}
}
/**
*
*/
private List getParsingTables(ITaskModel forTaskModel) {
List rules = new LinkedList<>();
for (ITask task : forTaskModel.getTasks()) {
if (task instanceof ISequence) {
// other task types will be handled implicitly
addRulesIfNotThere(rules, createProductionRules((ISequence) task));
}
}
List tables = new ArrayList();
int count = 0;
for (ITask task : forTaskModel.getTasks()) {
if (task instanceof ISequence) {
try {
tables.add(createParsingTable((ISequence) task, getRelevantRules(task, rules)));
}
catch (IllegalArgumentException e) {
Console.println(e.toString() + " " + ++count);
}
}
}
return tables;
}
/**
*
*/
private List createProductionRules(ISequence sequence) {
//new TaskTreeEncoder().encode(sequence, System.out);
List rules = new LinkedList();
List executionVariants = new ArrayList<>(sequence.getChildren().size());
int noOfOptionalChildren = 0;
for (ITask child : sequence.getChildren()) {
ExecutionVariants variants = getExecutionVariants(child);
if (variants.canBeOptional()) {
noOfOptionalChildren++;
}
executionVariants.add(variants);
}
// for iterations and selections, we create non terminals
// for optional children, we create multiple production for the current sequence
// all other children are just added
for (int i = 0; i < Math.pow(2, noOfOptionalChildren); i++) {
int childIndex = 0;
int optionalIndex = 0;
List rightHandSide = new ArrayList<>();
for (ITask child : sequence.getChildren()) {
boolean leaveout = false;
if (child instanceof IEventTask) {
rightHandSide.add(child);
childIndex++;
continue;
}
else if (executionVariants.get(childIndex).canBeOptional()) {
// child is optional, check if to be left out
if ((((int) Math.pow(2, optionalIndex)) & i) == 0) {
leaveout = true;
}
optionalIndex++;
}
if (leaveout) {
childIndex++;
continue;
}
Object childSymbol = null;
if (executionVariants.get(childIndex).size() > 1) {
// create selective production rules
childSymbol = sequence.getId() + "_sel" + childIndex;
int variantIndex = 0;
for (ExecutionVariant executionVariant : executionVariants.get(childIndex)) {
if (!executionVariant.canBeIterated) {
rules.add(new ProductionRule
((String) childSymbol,
new Object[] { getSymbol(executionVariant.task) }));
}
else {
// create iterative production rules
String iterationSymbol = childSymbol + "_it" + variantIndex;
rules.add(new ProductionRule
(iterationSymbol,
new Object[] { iterationSymbol, executionVariant.task }));
rules.add(new ProductionRule(iterationSymbol,
new Object[] { executionVariant.task }));
rules.add(new ProductionRule((String) childSymbol,
new Object[] { iterationSymbol }));
}
variantIndex++;
}
}
else {
childSymbol = getSymbol(executionVariants.get(childIndex).get(0).task);
}
if (isIteration(child)) {
// create iterative production rules
String iterationSymbol = sequence.getId() + "_it" + childIndex;
rules.add(new ProductionRule(iterationSymbol,
new Object[] { iterationSymbol, childSymbol }));
rules.add(new ProductionRule(iterationSymbol, new Object[] { childSymbol }));
childSymbol = iterationSymbol;
}
rightHandSide.add(childSymbol);
childIndex++;
}
rules.add(new ProductionRule(Integer.toString(sequence.getId()),
rightHandSide.toArray()));
}
return rules;
}
/**
*
*/
private boolean isIteration(ITask child) {
if (child instanceof IIteration) {
return true;
}
else if (child instanceof IOptional) {
return isIteration(((IOptional) child).getMarkedTask());
}
return false;
}
/**
*
*/
private Object getSymbol(ITask executionVariant) {
if (executionVariant instanceof IEventTask) {
return executionVariant;
}
else {
return Integer.toString(executionVariant.getId());
}
}
/**
*
*/
private ExecutionVariants getExecutionVariants(ITask task) {
if (task instanceof IOptional) {
ExecutionVariants result = getExecutionVariants(((IOptional) task).getMarkedTask());
result.setCanBeOptional();
return result;
}
else if (task instanceof ISelection) {
ExecutionVariants result = new ExecutionVariants();
for (ITask child : ((ISelection) task).getChildren()) {
result.addAll(getExecutionVariants(child));
}
return result;
}
else if (task instanceof IIteration) {
ExecutionVariants result = getExecutionVariants(((IIteration) task).getMarkedTask());
result.setCanBeIterated();
return result;
}
else {
ExecutionVariants result = new ExecutionVariants();
result.add(task);
return result;
}
}
/**
*
*/
private void addRulesIfNotThere(List rules,
List newRules)
{
for (ProductionRule newRule : newRules) {
boolean found = false;
for (ProductionRule candidate : rules) {
if (candidate.equals(newRule)) {
found = true;
break;
}
}
if (!found) {
rules.add(newRule);
}
}
}
/**
*
*/
private List getRelevantRules(ITask task, List rules) {
List relevantRules = new LinkedList<>();
Set handledNonTerminals = new HashSet<>();
Stack nonTerminals = new Stack();
nonTerminals.push((String) getSymbol(task));
// search for relevant rules that belong to the grammar initiated by the initial rule
do {
String nonTerminal = nonTerminals.pop();
handledNonTerminals.add(nonTerminal);
for (ProductionRule candidate : rules) {
if (candidate.leftHandSide.equals(nonTerminal)) {
relevantRules.add(candidate);
for (int i = 0; i < candidate.rightHandSide.length; i++) {
if ((candidate.rightHandSide[i] instanceof String) &&
!handledNonTerminals.contains((String) candidate.rightHandSide[i]))
{
nonTerminals.push((String) candidate.rightHandSide[i]);
}
}
}
}
}
while (nonTerminals.size() > 0);
return relevantRules;
}
/**
*
*/
private ParsingTable createParsingTable(ISequence task,
List rules)
{
ParsingTable table = new ParsingTable(task);
List fullRuleSet = new LinkedList<>(rules);
ProductionRule initialRule = new ProductionRule("S'", new Object[] { getSymbol(task), EOF });
fullRuleSet.add(0, initialRule);
ProductionRulePosition initialPosition = new ProductionRulePosition(initialRule, 0);
State initialState = new State();
initialState.add(initialPosition);
// create the state machine as typical for an LR(1) parser
List states = new LinkedList<>();
states.add(closure(initialState, fullRuleSet));
List edges = new LinkedList<>();
int noOfStates;
int noOfEdges;
do {
noOfStates = states.size();
noOfEdges = edges.size();
List newStates = new LinkedList();
List newEdges = new LinkedList();
for (State state : states) {
for (ProductionRulePosition position : state) {
if (position.getNextSymbol() != null) {
State newState = gotoFunction(state, position.getNextSymbol(), fullRuleSet);
if (newState.size() > 0) {
State existing = null;
for (State candidate : states) {
if (candidate.equals(newState)) {
existing = candidate;
break;
}
}
if (existing == null) {
// check if the state is one of the new states
for (State candidate : newStates) {
if (candidate.equals(newState)) {
existing = candidate;
break;
}
}
}
if (existing != null) {
newEdges.add(new Edge(state, existing, position.getNextSymbol()));
}
else {
newStates.add(newState);
newEdges.add(new Edge(state, newState, position.getNextSymbol()));
}
}
}
}
}
addStatesIfNotContained(states, newStates);
addEdgesIfNotContained(edges, newEdges);
}
while ((noOfStates != states.size()) && (noOfEdges != edges.size()));
/*System.out.println("\n\n\n\n");
new TaskTreeEncoder().encode(task, System.out);
System.out.println("\n");
for (ProductionRule rule : fullRuleSet) {
System.out.println(rule);
}
System.out.println("\n");
for (State state : states) {
System.out.println(state);
}
System.out.println("\n");
for (Edge edge : edges) {
System.out.println
("edge from " + edge.source.id + " to " + edge.dest.id + " on " + edge.symbol);
}*/
// now create the table based on the states and edges
for (Edge edge : edges) {
if ((edge.symbol instanceof IEventTask) || (edge.symbol == EOF)) {
table.addShift(edge.dest, edge.source, edge.symbol);
}
else {
table.addGoto(edge.dest, edge.source, edge.symbol);
}
}
for (State state : states) {
for (ProductionRulePosition position : state) {
if (position.getNextSymbol() == null) {
Set followSet =
getFollowSet(position.rule.leftHandSide, initialRule, fullRuleSet);
for (Object symbol : followSet) {
table.addReduce(state, symbol, position.rule);
}
}
}
}
/*System.out.println("\n");
System.out.println(task);
System.out.println("\n");
System.out.println(table);
List> testinputs = new LinkedList<>();
for (ITaskInstance instance : task.getInstances()) {
final List eventTasks = new ArrayList<>();
instance.accept(new DefaultTaskInstanceTraversingVisitor() {
@Override
public void visit(IEventTaskInstance eventTaskInstance) {
eventTasks.add(eventTaskInstance.getEventTask());
}
});
testinputs.add(eventTasks);
}
List tables = new LinkedList<>();
tables.add(table);
parse(testinputs, tables);*/
return table;
}
/**
*
*/
private Set getFollowSet(String leftHandSide,
ProductionRule initialRule,
List rules)
{
// search for all elements that may follow the given left hand side.
// consider also other non terminals whose production rules have a right hand side
// ending with the given left hand side
Set result = new HashSet<>();
List positions = new ArrayList();
int index = 0;
positions.add
(new ProductionRulePosition(new ProductionRule(leftHandSide, new Object[] {}), 0));
while (index < positions.size()) {
ProductionRulePosition productionRulePosition = positions.get(index++);
String nonTerminal = productionRulePosition.rule.leftHandSide;
List newPositions = new LinkedList<>();
if (productionRulePosition.getNextSymbol() == null) {
// we are at the end of the production rule. Add further production rule positions
// for all parent production rules
for (ProductionRule candidate : rules) {
for (int i = 0; i < candidate.rightHandSide.length; i++) {
if (nonTerminal.equals(candidate.rightHandSide[i])) {
newPositions.add(new ProductionRulePosition(candidate, i + 1));
}
}
}
}
else {
// we are in the middle of a rule. If the next symbol is a terminal, add it to
// the resulting set. If not, add all rules of the respective non terminal with
// position 0 to the stack
if ((productionRulePosition.getNextSymbol() instanceof IEventTask) ||
(productionRulePosition.getNextSymbol() == EOF))
{
result.add(productionRulePosition.getNextSymbol());
}
else {
for (ProductionRule candidate : rules) {
if (candidate.leftHandSide.equals(productionRulePosition.getNextSymbol())) {
newPositions.add(new ProductionRulePosition(candidate, 0));
}
}
}
}
for (ProductionRulePosition newPosition : newPositions) {
boolean found = false;
for (ProductionRulePosition posCandidate : positions) {
if (posCandidate.equals(newPosition)) {
found = true;
break;
}
}
if (!found) {
positions.add(newPosition);
}
}
}
return result;
}
/**
*
*/
private State closure(State state, List rules) {
State closure = new State(state);
int statesize;
do {
statesize = closure.size();
List newPositions = new LinkedList<>();
for (ProductionRulePosition position : closure) {
Object nextSymbol = position.getNextSymbol();
if (nextSymbol != null) {
for (ProductionRule candidate : rules) {
if (candidate.leftHandSide.equals(nextSymbol)) {
newPositions.add(new ProductionRulePosition(candidate, 0));
}
}
}
}
for (ProductionRulePosition newPosition : newPositions) {
boolean alreadyContained = false;
for (ProductionRulePosition existing : closure) {
if ((existing.rule == newPosition.rule) &&
(existing.position == newPosition.position))
{
alreadyContained = true;
break;
}
}
if (!alreadyContained) {
closure.add(newPosition);
}
}
}
while (statesize != closure.size());
return closure;
}
/**
*
*/
private State gotoFunction(State state, Object nextSymbol, List rules) {
State result = new State();
for (ProductionRulePosition position : state) {
if (nextSymbol.equals(position.getNextSymbol())) {
ProductionRulePosition nextPosition = position.advance();
if (nextPosition != null) {
result.add(nextPosition);
}
}
}
return closure(result, rules);
}
/**
*
*/
private void addStatesIfNotContained(List states, List newStates) {
for (State newState : newStates) {
boolean found = false;
for (State candidate : states) {
if (candidate.equals(newState)) {
found = true;
break;
}
}
if (!found) {
states.add(newState);
}
else {
throw new IllegalStateException
("the algorithm should reuse existing states and not add them again");
}
}
}
/**
*
*/
private void addEdgesIfNotContained(List edges, List newEdges) {
for (Edge newEdge : newEdges) {
boolean found = false;
for (Edge candidate : edges) {
if (candidate.equals(newEdge)) {
found = true;
break;
}
}
if (!found) {
edges.add(newEdge);
}
}
}
/**
*
*/
private int parse(List> inputs,
List parsingTables,
Statistics statistics)
{
int sessionIndex = 0;
int allActions = 0;
ParsingTableIndex tableIndex = new ParsingTableIndex(parsingTables, statistics);
for (List input : inputs) {
System.out.print("parsing session " + (sessionIndex + 1) + "/" + inputs.size() + ": ");
List currentParsers = new LinkedList<>();
int index = 0;
for (IEventTask token : input) {
allActions++;
index++;
for (ParsingTable table : tableIndex.getRelevantTables(token)) {
currentParsers.add(new Parser(table));
}
//System.out.println(currentParsers.size() + " " + token);
List continuingParsers = new LinkedList<>();
for (Parser parser : currentParsers) {
Parser.Result result = parser.handleToken(token);
if (result == Parser.Result.CONTINUE) {
Parser alternative = getParserInSameState(continuingParsers, parser);
if ((alternative == null) ||
(alternative.noOfParsedTokens < parser.noOfParsedTokens))
{
continuingParsers.add(parser);
if (parser.checkSuccess()) {
//System.out.println("parser is continuing and also successing");
statistics.addCoveredActions
(parser.table.sequence, sessionIndex, input.size(),
index - parser.getNoOfParsedTokens(), index - 1);
}
}
}
else if (result == Parser.Result.SUCCESS) {
statistics.addCoveredActions
(parser.table.sequence, sessionIndex, input.size(),
index - parser.getNoOfParsedTokens(), index - 2);
}
}
currentParsers = continuingParsers;
}
for (Parser parser : currentParsers) {
if (parser.checkSuccess()) {
statistics.addCoveredActions
(parser.table.sequence, sessionIndex, input.size(),
index - parser.getNoOfParsedTokens(), index - 1);
}
}
System.out.println
("parsed " + statistics.getCoveredActions(sessionIndex) + " of " + input.size() +
" actions");
sessionIndex++;
}
System.out.println
("parsed " + statistics.getRecalledActions() + " of " + allActions + " actions in " +
inputs.size() + " sessions (" + (100 * statistics.getRecalledActions() / allActions) +
"%)");
return statistics.getRecalledActions();
}
/**
*
*/
private Parser getParserInSameState(List existingParsers, Parser parser) {
Stack stack2 = parser.stack;
PARSER:
for (Parser existing : existingParsers) {
if (existing.table != parser.table) {
continue;
}
Stack stack1 = existing.stack;
if (stack1.size() == stack2.size()) {
Iterator it1 = stack1.iterator();
Iterator it2 = stack1.iterator();
while (it1.hasNext()) {
StackEntry entry1 = it1.next();
StackEntry entry2 = it2.next();
if (entry1.state != entry2.state) {
continue PARSER;
}
if (entry1.symbol instanceof IEventTask) {
if (entry1.symbol != entry2.symbol) {
continue PARSER;
}
}
else if ((entry1.symbol != null) && (!entry1.symbol.equals(entry2.symbol))) {
continue PARSER;
}
else if (entry1.symbol != entry2.symbol) {
continue PARSER;
}
}
// parsers are in same state
return existing;
}
}
return null;
}
/**
*
*/
private static class Parser {
/** */
private enum Result {
CONTINUE, FAIL, SUCCESS
}
/** */
private ParsingTable table;
/** */
private Stack stack = new Stack<>();
/** */
private int noOfParsedTokens = 0;
/**
*
*/
private Parser(ParsingTable table) {
this.table = table;
stack.push(new StackEntry(null, table.getInitialState()));
}
/**
*
*/
private int getNoOfParsedTokens() {
return noOfParsedTokens;
}
/**
*
*/
private boolean checkSuccess() {
// check the potential success of a copy of the stack to allow for parsing further
// tokens that are repetitions also allowed by the parser
Stack stackCopy = new Stack<>();
for (StackEntry entry : stack) {
stackCopy.push(entry);
}
Action action;
do {
action = table.getAction(stackCopy.peek().state, EOF);
if ((action != null) && (action.type == Action.Type.SHIFT)) {
return true;
}
else if ((action == null) || (action.type != Action.Type.REDUCE)) {
return false;
}
ProductionRule rule = action.rule;
//System.out.println(" reducing " + rule);
for (int i = rule.rightHandSide.length - 1; i >= 0; i--) {
/*StackEntry entry = */stackCopy.pop();
/*if (!entry.symbol.equals(rule.rightHandSide[i])) {
throw new RuntimeException("reduction seems to be wrong");
}*/
}
Action gotoAct = table.getAction(stackCopy.peek().state, rule.leftHandSide);
State nextState = stackCopy.peek().state;
if (gotoAct != null) {
//System.out.println(" performing goto to " + gotoAct.dest.id);
nextState = gotoAct.dest;
}
stackCopy.push(new StackEntry(rule.leftHandSide, nextState));
}
while (action != null);
return true;
}
/**
*
*/
private Result handleToken(IEventTask token) {
noOfParsedTokens ++;
Action action = table.getAction(stack.peek().state, token);
if (action == null) {
if (checkSuccess()) {
return Result.SUCCESS;
}
else {
return Result.FAIL;
}
}
/*System.out.println(" " + stack);
System.out.println(" " + token);
System.out.println
(" action for " + stack.peek().state.id + " on " + token + " is " + action);*/
while (action.type == Action.Type.REDUCE) {
ProductionRule rule = action.rule;
//System.out.println(" reducing " + rule);
for (int i = rule.rightHandSide.length - 1; i >= 0; i--) {
/*StackEntry entry = */stack.pop();
/*if (!entry.symbol.equals(rule.rightHandSide[i])) {
throw new RuntimeException("reduction seems to be wrong");
}*/
}
Action gotoAct = table.getAction(stack.peek().state, rule.leftHandSide);
State nextState = stack.peek().state;
if (gotoAct != null) {
//System.out.println(" performing goto to " + gotoAct.dest.id);
nextState = gotoAct.dest;
}
stack.push(new StackEntry(rule.leftHandSide, nextState));
action = table.getAction(stack.peek().state, token);
if (action == null) {
if (checkSuccess()) {
return Result.SUCCESS;
}
else {
return Result.FAIL;
}
}
}
if (action.type == Action.Type.SHIFT) {
//System.out.println(" shift to " + action.dest.id);
stack.push(new StackEntry(token, action.dest));
}
else if (action.type == Action.Type.GOTO) {
//System.out.println(" unexpected goto " + action.dest.id);
stack.peek().state = action.dest;
}
return Result.CONTINUE;
}
}
/**
*
*/
private static class ParsingTable {
/** */
private ISequence sequence;
/** */
private Map> table = new IdentityHashMap<>();
/**
*
*/
private ParsingTable(ISequence sequence) {
this.sequence = sequence;
}
/**
*
*/
private void addShift(State dest, State source, Object symbol) {
List row = table.get(source);
if (row == null) {
row = new LinkedList();
table.put(source, row);
}
//System.out.println("adding shift " + dest.id + " for " + source.id + "," + symbol);
row.add(new ParsingTableEntry(symbol, new Action(Action.Type.SHIFT, dest)));
}
/**
*
*/
private void addGoto(State dest, State source, Object symbol) {
List row = table.get(source);
if (row == null) {
row = new LinkedList();
table.put(source, row);
}
//System.out.println("adding goto " + dest.id + " for " + source.id + "," + symbol);
row.add(new ParsingTableEntry(symbol, new Action(Action.Type.GOTO, dest)));
}
/**
*
*/
private void addReduce(State source, Object symbol, ProductionRule rule) {
List row = table.get(source);
if (row == null) {
row = new LinkedList();
table.put(source, row);
}
for (ParsingTableEntry entry : row) {
if (entry.symbol.equals(symbol)) {
System.out.println("conflict for " + source.id + " and terminal " + symbol +
": " + entry.action + " " + new Action(rule));
throw new IllegalArgumentException("creating shift/reduce conflict");
}
}
row.add(new ParsingTableEntry(symbol, new Action(rule)));
}
/**
*
*/
private State getInitialState() {
for (State candidate : table.keySet()) {
for (ProductionRulePosition position : candidate) {
if ((position.position == 0) && (position.rule.leftHandSide.equals("S'"))) {
return candidate;
}
}
}
return null;
}
/**
*
*/
private List getInitialTokens() {
State initialState = getInitialState();
List result = new LinkedList<>();
for (ParsingTableEntry entry : table.get(initialState)) {
if (entry.symbol instanceof IEventTask) {
result.add((IEventTask) entry.symbol);
}
}
return result;
}
/**
*
*/
private Action getAction(State state, Object symbol) {
List row = table.get(state);
if (row != null) {
if (symbol instanceof IEventTask) {
for (ParsingTableEntry entry : row) {
if (entry.symbol == symbol) {
return entry.action;
}
}
}
else {
for (ParsingTableEntry entry : row) {
if (entry.symbol.equals(symbol)) {
return entry.action;
}
}
}
}
return null;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
Set eventTasks = new HashSet<>();
eventTasks.add(EOF);
Set symbols = new HashSet<>();
Set states = new HashSet<>();
for (Map.Entry> entry : table.entrySet()) {
for (ParsingTableEntry tableEntry : entry.getValue()) {
if (tableEntry.symbol instanceof IEventTask) {
eventTasks.add((IEventTask) tableEntry.symbol);
}
else if (tableEntry.symbol instanceof String) {
symbols.add((String) tableEntry.symbol);
}
}
states.add(entry.getKey());
}
StringBuffer result = new StringBuffer();
result.append("\t|");
for (Object task : eventTasks) {
if (task instanceof IEventTask) {
result.append(((IEventTask) task).getId());
}
else {
result.append("EOF");
}
result.append("\t|");
}
for (String symbol : symbols) {
result.append(symbol);
result.append("\t|");
}
result.append('\n');
result.append("--------------------------------------------------------------------\n");
for (State state : states) {
result.append(state.id);
result.append("\t|");
for (Object task : eventTasks) {
Action act = null;
if (table.containsKey(state)) {
act = getAction(state, task);
}
if (act != null) {
result.append(act);
}
result.append("\t|");
}
for (String symbol : symbols) {
Action act = null;
if (table.containsKey(state)) {
act = getAction(state, symbol);
}
if (act != null) {
result.append(act);
}
result.append("\t|");
}
result.append('\n');
}
return result.toString();
}
}
/**
*
*/
private static class ParsingTableEntry {
/** */
private Object symbol;
/** */
private Action action;
/**
*
*/
private ParsingTableEntry(Object symbol, Action action) {
this.symbol = symbol;
this.action = action;
}
}
/**
*
*/
private static class Action {
private enum Type {
SHIFT, GOTO, REDUCE
}
/** */
private Type type;
/** */
private State dest;
/** */
private ProductionRule rule;
/**
*
*/
private Action(Type type, State dest) {
this.type = type;
this.dest = dest;
this.rule = null;
}
/**
*
*/
private Action(ProductionRule rule) {
this.type = Type.REDUCE;
this.dest = null;
this.rule = rule;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
switch (type) {
case SHIFT: return "s" + dest.id;
case GOTO: return "g" + dest.id;
case REDUCE: return "r" + rule.id;
}
throw new IllegalStateException("action type must be one of shift, goto, and reduce");
}
}
/**
*
*/
private static class ParsingTableIndex {
/** */
private Map> index = new HashMap<>();
/**
*
*/
private ParsingTableIndex(List allTables,
Statistics statistics)
{
for (ParsingTable table : allTables) {
statistics.addCheckedSequence(table.sequence);
for (IEventTask firstToken : table.getInitialTokens()) {
IEventTaskInstance exampleinstance =
(IEventTaskInstance) firstToken.getInstances().iterator().next();
List group = index.get(exampleinstance.getEvent().getTarget());
if (group == null) {
group = new LinkedList<>();
index.put(exampleinstance.getEvent().getTarget(), group);
}
group.add(table);
}
}
}
/**
*
*/
private List getRelevantTables(IEventTask token) {
IEventTaskInstance exampleinstance =
(IEventTaskInstance) token.getInstances().iterator().next();
List result = index.get(exampleinstance.getEvent().getTarget());
if (result != null) {
return result;
}
else {
return new LinkedList<>();
}
}
}
/**
*
*/
private static class ProductionRule {
/** */
private String leftHandSide;
/** */
private Object[] rightHandSide;
/** */
private static int IDCOUNTER = 0;
/** */
private final int id = IDCOUNTER++;
/**
*
*/
private ProductionRule(String leftHandSide, Object[] rightHandSide) {
this.leftHandSide = leftHandSide;
this.rightHandSide = rightHandSide;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
StringBuffer result = new StringBuffer();
result.append(id);
result.append(": ");
result.append(leftHandSide);
result.append(" ---> ");
for (Object symbol : rightHandSide) {
result.append(symbol);
result.append(" ");
}
return result.toString();
}
/* (non-Javadoc)
* @see java.lang.Object#equals(java.lang.Object)
*/
@Override
public boolean equals(Object obj) {
if (obj == this) {
return true;
}
if (!(obj instanceof ProductionRule)) {
return false;
}
ProductionRule other = (ProductionRule) obj;
if (!other.leftHandSide.equals(this.leftHandSide)) {
return false;
}
if (other.rightHandSide.length != this.rightHandSide.length) {
return false;
}
for (int i = 0; i < other.rightHandSide.length; i++) {
if (!other.rightHandSide[i].equals(this.rightHandSide[i])) {
return false;
}
}
return true;
}
/* (non-Javadoc)
* @see java.lang.Object#hashCode()
*/
@Override
public int hashCode() {
return leftHandSide.hashCode();
}
}
/**
*
*/
private static class ProductionRulePosition {
/** */
private ProductionRule rule;
/** */
private int position;
/**
*
*/
private ProductionRulePosition(ProductionRule rule, int position) {
this.rule = rule;
this.position = position;
}
/**
*
*/
private ProductionRulePosition advance() {
if (position < rule.rightHandSide.length) {
return new ProductionRulePosition(rule, position + 1);
}
else {
return null;
}
}
/**
*
*/
private Object getNextSymbol() {
if (position < rule.rightHandSide.length) {
return rule.rightHandSide[position];
}
else {
return null;
}
}
/* (non-Javadoc)
* @see java.lang.Object#equals(java.lang.Object)
*/
@Override
public boolean equals(Object obj) {
return (obj instanceof ProductionRulePosition) &&
(this.rule.equals(((ProductionRulePosition) obj).rule)) &&
(this.position == ((ProductionRulePosition) obj).position);
}
/* (non-Javadoc)
* @see java.lang.Object#hashCode()
*/
@Override
public int hashCode() {
return this.rule.hashCode() + this.position;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return rule + " (position " + position + ")";
}
}
/**
*
*/
private static class State extends ArrayList {
/** */
private static final long serialVersionUID = 1L;
/** */
private static int IDCOUNTER = 0;
/** */
private final int id = IDCOUNTER++;
/**
*
*/
private State() {
super();
}
/**
*
*/
private State(Collection extends ProductionRulePosition> c) {
super(c);
}
/* (non-Javadoc)
* @see java.util.AbstractList#equals(java.lang.Object)
*/
@Override
public boolean equals(Object other) {
if (!(other instanceof State)) {
return false;
}
State otherState = (State) other;
if (otherState.size() != this.size()) {
return false;
}
for (ProductionRulePosition position : this) {
boolean positionFound = false;
for (ProductionRulePosition candidatePosition : otherState) {
if (position.equals(candidatePosition)) {
positionFound = true;
break;
}
}
if (!positionFound) {
return false;
}
}
return true;
}
/* (non-Javadoc)
* @see java.util.AbstractCollection#toString()
*/
@Override
public String toString() {
StringBuffer result = new StringBuffer();
result.append("State ");
result.append(id);
result.append('\n');
for (ProductionRulePosition pos : this) {
result.append(" ");
result.append(pos);
result.append('\n');
}
return result.toString();
}
}
/**
*
*/
private static class Edge {
/** */
private State source;
/** */
private State dest;
/** */
private Object symbol;
/**
*
*/
private Edge(State source, State dest, Object symbol) {
this.source = source;
this.dest = dest;
this.symbol = symbol;
}
/* (non-Javadoc)
* @see java.lang.Object#equals(java.lang.Object)
*/
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
else {
return (obj instanceof Edge) && (((Edge) obj).source.equals(this.source)) &&
(((Edge) obj).dest.equals(this.dest)) &&
(((Edge) obj).symbol.equals(this.symbol));
}
}
/* (non-Javadoc)
* @see java.lang.Object#hashCode()
*/
@Override
public int hashCode() {
return this.symbol.hashCode();
}
}
/**
*
*/
private static class ExecutionVariants extends ArrayList {
/** */
private static final long serialVersionUID = 1L;
/**
*
*/
private void setCanBeOptional() {
for (ExecutionVariant variant : this) {
variant.canBeOptional = true;
}
}
/**
*
*/
private boolean canBeOptional() {
for (ExecutionVariant variant : this) {
if (variant.canBeOptional) {
return true;
}
}
return false;
}
/**
*
*/
private void add(ITask task) {
super.add(new ExecutionVariant(task));
}
/**
*
*/
private void setCanBeIterated() {
for (ExecutionVariant variant : this) {
variant.canBeIterated = true;
}
}
}
/**
*
*/
private static class ExecutionVariant {
/** */
private ITask task;
/** */
private boolean canBeOptional = false;
/** */
private boolean canBeIterated = false;
/**
*
*/
private ExecutionVariant(ITask task) {
this.task = task;
}
}
/**
*
*/
private static class StackEntry {
/** */
private Object symbol;
/** */
private State state;
/**
*
*/
private StackEntry(Object symbol, State state) {
super();
this.symbol = symbol;
this.state = state;
}
/* (non-Javadoc)
* @see java.lang.Object#toString()
*/
@Override
public String toString() {
return "(" + symbol + "," + state.id + ")";
}
}
/**
*
*/
private static class Statistics {
/** */
private ITaskModel comparedModel;
/** */
private ITaskModel comparedWithModel;
/** */
private Map sessionCoverage = new HashMap<>();
/** */
private Map> sequenceCoverage = new HashMap<>();
/** */
private int allEventsOfComparedModel;
/** */
private int allSequencesOfComparedModel;
/** */
private int eventsCoveredBySequencesOfComparedModel;
/** */
private int allEventsOfComparedWithModel;
/** */
private int allSequencesOfComparedWithModel;
/** */
private int eventsCoveredBySequencesOfComparedWithModel;
/**
*
*/
private Statistics(ITaskModel comparedModel, ITaskModel comparedWithModel) {
super();
this.comparedModel = comparedModel;
this.comparedWithModel = comparedWithModel;
this.allEventsOfComparedModel = getAllEvents(comparedModel);
Set sequences = getSequences(comparedModel);
this.allSequencesOfComparedModel = sequences.size();
this.eventsCoveredBySequencesOfComparedModel =
TaskTreeUtils.getNoOfEventsCoveredBySequences(sequences);
this.allEventsOfComparedWithModel = getAllEvents(comparedWithModel);
sequences = getSequences(comparedWithModel);
this.allSequencesOfComparedWithModel = sequences.size();
this.eventsCoveredBySequencesOfComparedWithModel =
TaskTreeUtils.getNoOfEventsCoveredBySequences(sequences);
}
/**
*
*/
private Set getSequences(ITaskModel model) {
Set result = new HashSet<>();
for (ITask candidate : model.getTasks()) {
if (candidate instanceof ISequence) {
result.add((ISequence) candidate);
}
}
return result;
}
/**
*
*/
private int getAllEvents(ITaskModel model) {
int allEvents = 0;
for (ITask task : model.getTasks()) {
if (task instanceof IEventTask) {
allEvents += task.getInstances().size();
}
}
return allEvents;
}
/**
*
*/
private int getCoveredActions(int sessionIndex) {
boolean[] coveredActions = sessionCoverage.get(sessionIndex);
if (coveredActions == null) {
return 0;
}
else {
int counter = 0;
for (int i = 0; i < coveredActions.length; i++) {
if (coveredActions[i]) {
counter++;
}
}
return counter;
}
}
/**
*
*/
private int getRecalledActions() {
int overallCoverage = 0;
for (boolean[] coveredActions : sessionCoverage.values()) {
for (int i = 0; i < coveredActions.length; i++) {
if (coveredActions[i]) {
overallCoverage++;
}
}
}
return overallCoverage;
}
/**
*
*/
private int getRecalledActionsOf(Set sequences) {
Map combinedCoveredSessions = new HashMap<>();
for (ISequence sequence : sequences) {
Map coveredSessions = sequenceCoverage.get(sequence);
if (coveredSessions != null) {
for (Map.Entry entry : coveredSessions.entrySet()) {
boolean[] combinedSession = combinedCoveredSessions.get(entry.getKey());
if (combinedSession == null) {
combinedSession = new boolean[entry.getValue().length];
combinedCoveredSessions.put(entry.getKey(), combinedSession);
}
for (int i = 0; i < combinedSession.length; i++) {
if (entry.getValue()[i]) {
combinedSession[i] = true;
}
}
}
}
}
int overallCoverage = 0;
for (boolean[] coveredActions : combinedCoveredSessions.values()) {
for (int i = 0; i < coveredActions.length; i++) {
if (coveredActions[i]) {
overallCoverage++;
}
}
}
return overallCoverage;
}
/**
*
*/
private void addCheckedSequence(ISequence coveringSequence) {
Map coveredSessions = sequenceCoverage.get(coveringSequence);
if (coveredSessions == null) {
coveredSessions = new HashMap<>();
sequenceCoverage.put(coveringSequence, coveredSessions);
}
}
/**
*
*/
private void addCoveredActions(ISequence coveringSequence,
int sessionIndex,
int sessionSize,
int indexFirstAction,
int indexLastAction)
{
boolean[] coveredActions = sessionCoverage.get(sessionIndex);
if (coveredActions == null) {
coveredActions = new boolean[sessionSize];
sessionCoverage.put(sessionIndex, coveredActions);
}
for (int i = indexFirstAction; i <= indexLastAction; i++) {
coveredActions[i] = true;
}
Map coveredSessions = sequenceCoverage.get(coveringSequence);
if (coveredSessions == null) {
coveredSessions = new HashMap<>();
sequenceCoverage.put(coveringSequence, coveredSessions);
}
coveredActions = coveredSessions.get(sessionIndex);
if (coveredActions == null) {
coveredActions = new boolean[sessionSize];
coveredSessions.put(sessionIndex, coveredActions);
}
for (int i = indexFirstAction; i <= indexLastAction; i++) {
coveredActions[i] = true;
}
}
/**
*
*/
private void dump(PrintStream out) {
Set mostProminentSequences =
TaskTreeUtils.getMostProminentSequences(comparedModel, sequenceCoverage.keySet());
int eventsCoveredByAllSequences =
TaskTreeUtils.getNoOfEventsCoveredBySequences(sequenceCoverage.keySet());
int eventsCoveredByMostProminent =
TaskTreeUtils.getNoOfEventsCoveredBySequences(mostProminentSequences);
int recalledActions = getRecalledActions();
int recalledActionsMostProminent = getRecalledActionsOf(mostProminentSequences);
out.println("\nComparison Statistics");
out.println("=======================================================================");
out.println("compared model: " + comparedModel);
out.println(" all actions in sessions: " +
allEventsOfComparedModel);
out.println(" all sequences of model: " +
allSequencesOfComparedModel);
out.println(" checked sequences of model: " +
formatPerc(sequenceCoverage.keySet().size(), allSequencesOfComparedModel));
out.println(" most prominent checked sequences of model: " +
mostProminentSequences.size());
out.println(" actions covered by all sequences: " +
formatPerc(eventsCoveredBySequencesOfComparedModel, allEventsOfComparedModel));
out.println(" actions covered by checked sequences: " +
formatPerc(eventsCoveredByAllSequences, allEventsOfComparedModel));
out.println("actions covered by most prominent checked sequences: " +
formatPerc(eventsCoveredByMostProminent, allEventsOfComparedModel));
out.println();
out.println("compared with: " + comparedWithModel);
out.println(" all actions in sessions: " +
allEventsOfComparedWithModel);
out.println(" all sequences of model: " +
allSequencesOfComparedWithModel);
out.println(" actions covered by all sequences: " +
formatPerc(eventsCoveredBySequencesOfComparedWithModel,
allEventsOfComparedWithModel));
out.println();
out.println(" actions covered by checked sequences: " +
formatPerc(recalledActions, allEventsOfComparedWithModel));
out.println(" actions covered by most prominent sequences: " +
formatPerc(recalledActionsMostProminent, allEventsOfComparedWithModel));
out.println();
out.print("CSV: ");
out.print(allEventsOfComparedModel);
out.print(";");
out.print(allSequencesOfComparedModel);
out.print(";");
out.print(sequenceCoverage.keySet().size());
out.print(";");
out.print((double) sequenceCoverage.keySet().size() / allSequencesOfComparedModel);
out.print(";");
out.print(mostProminentSequences.size());
out.print(";");
out.print(eventsCoveredBySequencesOfComparedModel);
out.print(";");
out.print((double) eventsCoveredBySequencesOfComparedModel / allEventsOfComparedModel);
out.print(";");
out.print(eventsCoveredByAllSequences);
out.print(";");
out.print((double) eventsCoveredByAllSequences / allEventsOfComparedModel);
out.print(";");
out.print(eventsCoveredByMostProminent);
out.print(";");
out.print((double) eventsCoveredByMostProminent / allEventsOfComparedModel);
out.print(";");
out.print(allEventsOfComparedWithModel);
out.print(";");
out.print(allSequencesOfComparedWithModel);
out.print(";");
out.print(eventsCoveredBySequencesOfComparedWithModel);
out.print(";");
out.print((double) eventsCoveredBySequencesOfComparedWithModel / allEventsOfComparedWithModel);
out.print(";");
out.print(recalledActions);
out.print(";");
out.print((double) recalledActions / allEventsOfComparedWithModel);
out.print(";");
out.print(recalledActionsMostProminent);
out.print(";");
out.print((double) recalledActionsMostProminent / allEventsOfComparedWithModel);
out.println();
out.println();
/*for (final ISequence sequence : sequenceCoverage.keySet()) {
Set tmp = new HashSet<>();
tmp.add(sequence);
if (comparedModel.getTaskInfo(sequence).getMeasureValue(TaskMetric.EVENT_COVERAGE) >= getRecalledActionsOf(tmp)) {
continue;
}
System.out.println();
System.out.println(comparedModel.getTaskInfo(sequence).getMeasureValue(TaskMetric.EVENT_COVERAGE) +
" " + getRecalledActionsOf(tmp));
new TaskTreeEncoder().encode(sequence, System.out);
final List eventList = new LinkedList<>();
int sessionIndex = 0;
for (IUserSession session : comparedModel.getUserSessions()) {
sessionIndex++;
System.out.println("\ncoverage in session " + sessionIndex + " (" +
session.size() + ")");
//new TaskTreeEncoder().encode(session, System.out);
final int[] index = new int[1];
index[0] = 0;
for (ITaskInstance instance : session) {
instance.accept(new DefaultTaskInstanceTraversingVisitor() {
@Override
public void visit(IEventTaskInstance eventTaskInstance) {
eventList.add(eventTaskInstance);
}
@Override
public void visit(ISequenceInstance sequenceInstance) {
if (sequenceInstance.getTask() == sequence) {
eventList.clear();
}
super.visit(sequenceInstance);
if (sequenceInstance.getTask() == sequence) {
System.out.println("source: " + index[0] + " " + eventList);
}
}
});
index[0]++;
}
System.out.println("dest session " + comparedWithModel.getUserSessions().get(sessionIndex - 1).size());
eventList.clear();
final boolean[] covered = sequenceCoverage.get(sequence).get(sessionIndex - 1);
if (covered == null) {
System.out.println("no dest");
continue;
}
final int[] counter = new int[1];
index[0] = 0;
for (ITaskInstance instance : comparedWithModel.getUserSessions().get(sessionIndex - 1)) {
instance.accept(new DefaultTaskInstanceTraversingVisitor() {
@Override
public void visit(IEventTaskInstance eventTaskInstance) {
if (covered[counter[0]]) {
eventList.add(eventTaskInstance);
}
else {
if (eventList.size() > 0) {
System.out.println("dest: " + index[0] + " " + eventList);
}
eventList.clear();
}
counter[0]++;
}
});
index[0]++;
}
if (eventList.size() > 0) {
System.out.println("dest: " + eventList);
}
}
}*/
}
/**
*
*/
private String formatPerc(int part, int of) {
return (100 * part / of) + "% (" + part + "/" + of + ")";
}
}
}