code: package gr.uom.java.ast.decomposition.cfg;
  
  import gr.uom.java.ast.AbstractMethodDeclaration;
  
  import java.util.LinkedHashSet;
  import java.util.Map;
  import java.util.Set;
  import java.util.TreeSet;
  
  import org.eclipse.core.resources.IFile;
  import org.eclipse.jdt.core.dom.ClassInstanceCreation;
  import org.eclipse.jdt.core.dom.VariableDeclaration;
  
  public class PDGSlice extends Graph {
  	private PDG pdg;
  	private AbstractMethodDeclaration method;
  	private BasicBlock boundaryBlock;
  	private PDGNode nodeCriterion;
  	private AbstractVariable localVariableCriterion;
  	private Set<PDGNode> sliceNodes;
  	private Set<PDGNode> remainingNodes;
  	private Set<AbstractVariable> passedParameters;
  	private Set<PDGNode> indispensableNodes;
  	private Set<PDGNode> removableNodes;
  	private Set<AbstractVariable> returnedVariablesInOriginalMethod;
  	private IFile iFile;
  	private int methodSize;
  	
  	public PDGSlice(PDG pdg, BasicBlock boundaryBlock) {
  		super();
  		this.pdg = pdg;
  		this.method = pdg.getMethod();
  		this.iFile = pdg.getIFile();
  		this.methodSize = pdg.getTotalNumberOfStatements();
  		this.returnedVariablesInOriginalMethod = pdg.getReturnedVariables();
  		this.boundaryBlock = boundaryBlock;
  		Set<PDGNode> regionNodes = pdg.blockBasedRegion(boundaryBlock);
  		for(PDGNode node : regionNodes) {
  			nodes.add(node);
  		}
  		for(GraphEdge edge : pdg.edges) {
  			PDGDependence dependence = (PDGDependence)edge;
  			if(nodes.contains(dependence.src) && nodes.contains(dependence.dst)) {
  				if(dependence instanceof PDGDataDependence) {
  					PDGDataDependence dataDependence = (PDGDataDependence)dependence;
  					if(dataDependence.isLoopCarried()) {
  						PDGNode loopNode = dataDependence.getLoop().getPDGNode();
  						if(nodes.contains(loopNode))
  							edges.add(dataDependence);
  					}
  					else
  						edges.add(dataDependence);
  				}
  				else if(dependence instanceof PDGAntiDependence) {
  					PDGAntiDependence antiDependence = (PDGAntiDependence)dependence;
  					if(antiDependence.isLoopCarried()) {
  						PDGNode loopNode = antiDependence.getLoop().getPDGNode();
  						if(nodes.contains(loopNode))
  							edges.add(antiDependence);
  					}
  					else
  						edges.add(antiDependence);
  				}
  				else if(dependence instanceof PDGOutputDependence) {
  					PDGOutputDependence outputDependence = (PDGOutputDependence)dependence;
  					if(outputDependence.isLoopCarried()) {
  						PDGNode loopNode = outputDependence.getLoop().getPDGNode();
  						if(nodes.contains(loopNode))
  							edges.add(outputDependence);
  					}
  					else
  						edges.add(outputDependence);
  				}
  				else
  					edges.add(dependence);
  			}
  		}
  	}
  
  	public PDGSlice(PDG pdg, BasicBlock boundaryBlock, PDGNode nodeCriterion, AbstractVariable localVariableCriterion) {
  		this(pdg, boundaryBlock);
  		this.nodeCriterion = nodeCriterion;
  		this.localVariableCriterion = localVariableCriterion;
  		this.sliceNodes = new TreeSet<PDGNode>();
  		sliceNodes.addAll(computeSlice(nodeCriterion, localVariableCriterion));
  		this.remainingNodes = new TreeSet<PDGNode>();
  		remainingNodes.add(pdg.getEntryNode());
  		for(GraphNode node : pdg.nodes) {
  			PDGNode pdgNode = (PDGNode)node;
  			if(!sliceNodes.contains(pdgNode))
  				remainingNodes.add(pdgNode);
  		}
  		this.passedParameters = new LinkedHashSet<AbstractVariable>();
  		Set<PDGNode> nCD = new LinkedHashSet<PDGNode>();
  		Set<PDGNode> nDD = new LinkedHashSet<PDGNode>();
  		for(GraphEdge edge : pdg.edges) {
  			PDGDependence dependence = (PDGDependence)edge;
  			PDGNode srcPDGNode = (PDGNode)dependence.src;
  			PDGNode dstPDGNode = (PDGNode)dependence.dst;
  			if(dependence instanceof PDGDataDependence) {
  				PDGDataDependence dataDependence = (PDGDataDependence)dependence;
  				if(remainingNodes.contains(srcPDGNode) && sliceNodes.contains(dstPDGNode))
  					passedParameters.add(dataDependence.getData());
  				if(sliceNodes.contains(srcPDGNode) && remainingNodes.contains(dstPDGNode) &&
  						!dataDependence.getData().equals(localVariableCriterion) && !dataDependence.getData().isField())
  					nDD.add(srcPDGNode);
  			}
  			else if(dependence instanceof PDGControlDependence) {
  				if(sliceNodes.contains(srcPDGNode) && remainingNodes.contains(dstPDGNode))
  					nCD.add(srcPDGNode);
  			}
  		}
  		Set<PDGNode> controlIndispensableNodes = new LinkedHashSet<PDGNode>();
  		for(PDGNode p : nCD) {
  			for(AbstractVariable usedVariable : p.usedVariables) {
  				Set<PDGNode> pSliceNodes = computeSlice(p, usedVariable);
  				for(GraphNode node : pdg.nodes) {
  					PDGNode q = (PDGNode)node;
  					if(pSliceNodes.contains(q) || q.equals(p))
  						controlIndispensableNodes.add(q);
  				}
  			}
  		}
  		Set<PDGNode> dataIndispensableNodes = new LinkedHashSet<PDGNode>();
  		for(PDGNode p : nDD) {
  			for(AbstractVariable definedVariable : p.definedVariables) {
  				Set<PDGNode> pSliceNodes = computeSlice(p, definedVariable);
  				for(GraphNode node : pdg.nodes) {
  					PDGNode q = (PDGNode)node;
  					if(pSliceNodes.contains(q))
  						dataIndispensableNodes.add(q);
  				}
  			}
  		}
  		this.indispensableNodes = new TreeSet<PDGNode>();
  		indispensableNodes.addAll(controlIndispensableNodes);
  		indispensableNodes.addAll(dataIndispensableNodes);
  		this.removableNodes = new LinkedHashSet<PDGNode>();
  		for(GraphNode node : pdg.nodes) {
  			PDGNode pdgNode = (PDGNode)node;
  			if(!remainingNodes.contains(pdgNode) && !indispensableNodes.contains(pdgNode))
  				removableNodes.add(pdgNode);
  		}
  	}
  
  	public Set<VariableDeclaration> getVariableDeclarationsAndAccessedFieldsInMethod() {
  		return pdg.getVariableDeclarationsAndAccessedFieldsInMethod();
  	}
  
  	public AbstractMethodDeclaration getMethod() {
  		return method;
  	}
  
  	public IFile getIFile() {
  		return iFile;
  	}
  
  	public int getMethodSize() {
  		return methodSize;
  	}
  
  	public BasicBlock getBoundaryBlock() {
  		return boundaryBlock;
  	}
  
  	public PDGNode getExtractedMethodInvocationInsertionNode() {
  		return ((TreeSet<PDGNode>)sliceNodes).first();
  	}
  
  	public PDGNode getNodeCriterion() {
  		return nodeCriterion;
  	}
  
  	public AbstractVariable getLocalVariableCriterion() {
  		return localVariableCriterion;
  	}
  
  	public Set<PDGNode> getSliceNodes() {
  		return sliceNodes;
  	}
  
  	public Set<AbstractVariable> getPassedParameters() {
  		return passedParameters;
  	}
  
  	public Set<PDGNode> getRemovableNodes() {
  		return removableNodes;
  	}
  
  	public boolean nodeBelongsToBlockBasedRegion(GraphNode node) {
  		return nodes.contains(node);
  	}
  
  	public boolean edgeBelongsToBlockBasedRegion(GraphEdge edge) {
  		return edges.contains(edge);
  	}
  
  	public PDGNode getDeclarationOfVariableCriterion() {
  		PlainVariable plainVariable = localVariableCriterion.getInitialVariable();
  		for(PDGNode pdgNode : sliceNodes) {
  			if(pdgNode.declaresLocalVariable(plainVariable))
  				return pdgNode;
  		}
  		return null;
  	}
  
  	public boolean declarationOfVariableCriterionBelongsToSliceNodes() {
  		PlainVariable plainVariable = localVariableCriterion.getInitialVariable();
  		for(PDGNode pdgNode : sliceNodes) {
  			if(pdgNode.declaresLocalVariable(plainVariable))
  				return true;
  		}
  		return false;
  	}
  
  	public boolean declarationOfVariableCriterionBelongsToRemovableNodes() {
  		PlainVariable plainVariable = localVariableCriterion.getInitialVariable();
  		for(PDGNode pdgNode : removableNodes) {
  			if(pdgNode.declaresLocalVariable(plainVariable))
  				return true;
  		}
  		return false;
  	}
  
  	private boolean nodeCriterionIsDuplicated() {
  		Set<PDGNode> duplicatedNodes = new LinkedHashSet<PDGNode>();
  		duplicatedNodes.addAll(sliceNodes);
  		duplicatedNodes.retainAll(indispensableNodes);
  		if(duplicatedNodes.contains(nodeCriterion))
  			return true;
  		return false;
  	}
  
  	public boolean satisfiesRules() {
  		if(!nodeCritetionIsDeclarationOfVariableCriterion() && !nodeCriterionIsDuplicated() &&
  				!declarationOfVariableCriterionIsDuplicated() && !sliceContainsReturnStatement() &&
  				!variableCriterionIsReturnedVariableInOriginalMethod() &&
  				!returnStatementIsControlDependentOnSliceNode() &&
  				!containsDuplicateNodeWithStateChangingMethodInvocation() &&
  				!nonDuplicatedSliceNodeAntiDependsOnNonRemovableNode() &&
  				!nonDuplicatedSliceNodeOutputDependsOnNonRemovableNode() &&
  				!duplicatedSliceNodeWithClassInstantiationHasDependenceOnRemovableNode() &&
  				!sliceContainsBranchStatementWithoutInnermostLoop())
  			return true;
  		return false;
  	}
  
  	private boolean sliceContainsBranchStatementWithoutInnermostLoop() {
  		for(PDGNode node : sliceNodes) {
  			CFGNode cfgNode = node.getCFGNode();
  			if(cfgNode instanceof CFGBreakNode) {
  				CFGBreakNode breakNode = (CFGBreakNode)cfgNode;
  				CFGNode innerMostLoopNode = breakNode.getInnerMostLoopNode();
  				if(innerMostLoopNode != null && !sliceNodes.contains(innerMostLoopNode.getPDGNode()))
  					return true;
  			}
  			else if(cfgNode instanceof CFGContinueNode) {
  				CFGContinueNode continueNode = (CFGContinueNode)cfgNode;
  				CFGNode innerMostLoopNode = continueNode.getInnerMostLoopNode();
  				if(innerMostLoopNode != null && !sliceNodes.contains(innerMostLoopNode.getPDGNode()))
  					return true;
  			}
  		}
  		return false;
  	}
  
  	private boolean sliceContainsReturnStatement() {
  		for(PDGNode node : sliceNodes) {
  			if(node.getCFGNode() instanceof CFGExitNode)
  				return true;
  		}
  		return false;
  	}
  
  	private boolean declarationOfVariableCriterionIsDuplicated() {
  		Set<PDGNode> duplicatedNodes = new LinkedHashSet<PDGNode>();
  		duplicatedNodes.addAll(sliceNodes);
  		duplicatedNodes.retainAll(indispensableNodes);
  		for(PDGNode node : duplicatedNodes) {
  			if(node.declaresLocalVariable(localVariableCriterion) && !(node instanceof PDGTryNode))
  				return true;
  		}
  		return false;
  	}
  
  	private boolean returnStatementIsControlDependentOnSliceNode() {
  		for(GraphNode node : pdg.nodes) {
  			PDGNode pdgNode = (PDGNode)node;
  			if(pdgNode.getCFGNode() instanceof CFGExitNode) {
  				if(isControlDependentOnSliceNode(pdgNode))
  					return true;
  				if(sliceNodes.contains(pdgNode))
  					return true;
  			}
  		}
  		return false;
  	}
  
  	private boolean isControlDependentOnSliceNode(PDGNode node) {
  		for(GraphEdge edge : node.incomingEdges) {
  			PDGDependence dependence = (PDGDependence)edge;
  			if(dependence instanceof PDGControlDependence) {
  				PDGControlDependence controlDependence = (PDGControlDependence)dependence;
  				PDGNode srcPDGNode = (PDGNode)controlDependence.src;
  				if(sliceNodes.contains(srcPDGNode))
  					return true;
  				else
  					return isControlDependentOnSliceNode(srcPDGNode);
  			}
  		}
  		return false;
  	}
  
  	private boolean nonDuplicatedSliceNodeAntiDependsOnNonRemovableNode() {
  		Set<PDGNode> duplicatedNodes = new LinkedHashSet<PDGNode>();
  		duplicatedNodes.addAll(sliceNodes);
  		duplicatedNodes.retainAll(indispensableNodes);
  		for(PDGNode sliceNode : sliceNodes) {
  			if(!duplicatedNodes.contains(sliceNode)) {
  				for(GraphEdge edge : sliceNode.incomingEdges) {
  					PDGDependence dependence = (PDGDependence)edge;
  					if(edges.contains(dependence) && dependence instanceof PDGAntiDependence) {
  						PDGAntiDependence antiDependence = (PDGAntiDependence)dependence;
  						PDGNode srcPDGNode = (PDGNode)antiDependence.src;
  						if(!removableNodes.contains(srcPDGNode) && !nodeDependsOnNonRemovableNode(srcPDGNode, antiDependence.getData()))
  							return true;
  					}
  				}
  			}
  		}
  		return false;
  	}
  
  	private boolean nodeDependsOnNonRemovableNode(PDGNode node, AbstractVariable variable) {
  		for(GraphEdge edge : node.incomingEdges) {
  			PDGDependence dependence = (PDGDependence)edge;
  			if(edges.contains(dependence) && dependence instanceof PDGDataDependence) {
  				PDGDataDependence dataDependence = (PDGDataDependence)dependence;
  				if(dataDependence.getData().equals(variable)) {
  					PDGNode srcPDGNode = (PDGNode)dataDependence.src;
  					if(!removableNodes.contains(srcPDGNode))
  						return true;
  				}
  			}
  		}
  		return false;
  	}
  
  	private boolean nonDuplicatedSliceNodeOutputDependsOnNonRemovableNode() {
  		Set<PDGNode> duplicatedNodes = new LinkedHashSet<PDGNode>();
  		duplicatedNodes.addAll(sliceNodes);
  		duplicatedNodes.retainAll(indispensableNodes);
  		for(PDGNode sliceNode : sliceNodes) {
  			if(!duplicatedNodes.contains(sliceNode)) {
  				for(GraphEdge edge : sliceNode.incomingEdges) {
  					PDGDependence dependence = (PDGDependence)edge;
  					if(edges.contains(dependence) && dependence instanceof PDGOutputDependence) {
  						PDGOutputDependence outputDependence = (PDGOutputDependence)dependence;
  						PDGNode srcPDGNode = (PDGNode)outputDependence.src;
  						if(!removableNodes.contains(srcPDGNode))
  							return true;
  					}
  				}
  			}
  		}
  		return false;
  	}
  
  	private boolean duplicatedSliceNodeWithClassInstantiationHasDependenceOnRemovableNode() {
  		Set<PDGNode> duplicatedNodes = new LinkedHashSet<PDGNode>();
  		duplicatedNodes.addAll(sliceNodes);
  		duplicatedNodes.retainAll(indispensableNodes);
  		for(PDGNode duplicatedNode : duplicatedNodes) {
  			if(duplicatedNode.containsClassInstanceCreation()) {
  				Map<VariableDeclaration, ClassInstanceCreation> classInstantiations = duplicatedNode.getClassInstantiations();
  				for(VariableDeclaration variableDeclaration : classInstantiations.keySet()) {
  					for(GraphEdge edge : duplicatedNode.outgoingEdges) {
  						PDGDependence dependence = (PDGDependence)edge;
  						if(edges.contains(dependence) && dependence instanceof PDGDependence) {
  							PDGDependence dataDependence = (PDGDependence)dependence;
  							PDGNode dstPDGNode = (PDGNode)dataDependence.dst;
  							if(removableNodes.contains(dstPDGNode)) {
  								if(dstPDGNode.changesStateOfReference(variableDeclaration) ||
  										dstPDGNode.assignsReference(variableDeclaration) || dstPDGNode.accessesReference(variableDeclaration))
  									return true;
  							}
  						}
  					}
  				}
  			}
  		}
  		return false;
  	}
  
  	private boolean nodeCritetionIsDeclarationOfVariableCriterion() {
  		if(nodeCriterion.declaresLocalVariable(localVariableCriterion))
  			return true;
  		return false;
  	}
  
  	private boolean variableCriterionIsReturnedVariableInOriginalMethod() {
  		if(returnedVariablesInOriginalMethod.contains(localVariableCriterion))
  			return true;
  		return false;
  	}
  
  	private boolean containsDuplicateNodeWithStateChangingMethodInvocation() {
  		Set<PDGNode> duplicatedNodes = new LinkedHashSet<PDGNode>();
  		duplicatedNodes.addAll(sliceNodes);
  		duplicatedNodes.retainAll(indispensableNodes);
  		for(PDGNode node : duplicatedNodes) {
  			for(AbstractVariable stateChangingVariable : node.definedVariables) {
  				if(stateChangingVariable instanceof CompositeVariable) {
  					PlainVariable plainVariable = stateChangingVariable.getInitialVariable();
  					if(!sliceContainsDeclaration(plainVariable))
  						return true;
  				}
  				else if(stateChangingVariable instanceof PlainVariable) {
  					PlainVariable plainVariable = stateChangingVariable.getInitialVariable();
  					if(plainVariable.isField())
  						return true;
  				}
  			}
  		}
  		return false;
  	}
  
  	private boolean sliceContainsDeclaration(AbstractVariable variableDeclaration) {
  		for(PDGNode pdgNode : sliceNodes) {
  			if(pdgNode.declaresLocalVariable(variableDeclaration))
  				return true;
  		}
  		return false;
  	}
  
  	public Set<PDGNode> computeSlice(PDGNode nodeCriterion, AbstractVariable localVariableCriterion) {
  		Set<PDGNode> sliceNodes = new LinkedHashSet<PDGNode>();
  		if(nodeCriterion.definesLocalVariable(localVariableCriterion)) {
  			sliceNodes.addAll(traverseBackward(nodeCriterion, new LinkedHashSet<PDGNode>()));
  		}
  		else if(nodeCriterion.usesLocalVariable(localVariableCriterion)) {
  			Set<PDGNode> defNodes = getDefNodes(nodeCriterion, localVariableCriterion);
  			for(PDGNode defNode : defNodes) {
  				sliceNodes.addAll(traverseBackward(defNode, new LinkedHashSet<PDGNode>()));
  			}
  			sliceNodes.addAll(traverseBackward(nodeCriterion, new LinkedHashSet<PDGNode>()));
  		}
  		return sliceNodes;
  	}
  
  	public Set<PDGNode> computeSlice(PDGNode nodeCriterion) {
  		Set<PDGNode> sliceNodes = new LinkedHashSet<PDGNode>();
  		sliceNodes.addAll(traverseBackward(nodeCriterion, new LinkedHashSet<PDGNode>()));
  		return sliceNodes;
  	}
  
  	private Set<PDGNode> getDefNodes(PDGNode node, AbstractVariable localVariable) {
  		Set<PDGNode> defNodes = new LinkedHashSet<PDGNode>();
  		for(GraphEdge edge : node.incomingEdges) {
  			PDGDependence dependence = (PDGDependence)edge;
  			if(edges.contains(dependence) && dependence instanceof PDGDataDependence) {
  				PDGDataDependence dataDependence = (PDGDataDependence)dependence;
  				if(dataDependence.getData().equals(localVariable)) {
  					PDGNode srcPDGNode = (PDGNode)dependence.src;
  					defNodes.add(srcPDGNode);
  				}
  			}
  		}
  		return defNodes;
  	}
  
  	private Set<PDGNode> traverseBackward(PDGNode node, Set<PDGNode> visitedNodes) {
  		Set<PDGNode> sliceNodes = new LinkedHashSet<PDGNode>();
  		sliceNodes.add(node);
  		visitedNodes.add(node);
  		for(GraphEdge edge : node.incomingEdges) {
  			PDGDependence dependence = (PDGDependence)edge;
  			if(edges.contains(dependence) && !(dependence instanceof PDGAntiDependence) && !(dependence instanceof PDGOutputDependence)) {
  				PDGNode srcPDGNode = (PDGNode)dependence.src;
  				if(!visitedNodes.contains(srcPDGNode))
  					sliceNodes.addAll(traverseBackward(srcPDGNode, visitedNodes));
  			}
  		}
  		return sliceNodes;
  	}
  
  	public String toString() {
  		return "<" + localVariableCriterion + ", " + nodeCriterion.getId() + "> [B" + boundaryBlock.getId() + "]\n" +
  		sliceNodes + "\npassed parameters: " + passedParameters + "\nindispensable nodes: " + indispensableNodes;
  	}
  }
  