OnePassConstrainedAlgorithm.java

package edg.slicing;

import edg.constraint.*;
import edg.graph.EDG;
import edg.graph.Edge;
import edg.graph.LAST.Direction;
import edg.graph.Node;
import edg.work.EdgeWork;
import edg.work.NodeWork;
import edg.work.Work;
import edg.work.WorkList;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class OnePassConstrainedAlgorithm implements SlicingAlgorithm
{
	protected final EDG edg;
	public OnePassConstrainedAlgorithm(EDG edg) { this.edg = edg; }

	public Set<Node> slice(Node node)
	{
		final Set<Node> slice = new HashSet<>();
		if (node == null)
			return slice;

		final WorkList workList = new WorkList();
		workList.pend(new NodeWork(node, node, new Constraints()));
		this.traverse(Phase.OnePhase, workList);

		slice.addAll(workList.getDoneNodes());

		// Reset constraints to their original form after slicing the graph
//		edg.edgeSet().stream()
//				.filter(e -> e.getType() == Edge.Type.Flow || e.getType() == Edge.Type.Value)
//				.forEach(Edge::resetVisibleConstraint);

		return slice;
	}

	private void traverse(Phase phase, WorkList workList)
	{
		while (workList.hasMore())
		{
			final Work pendingWork = workList.next();
			final List<Work> newWorks = this.processWork(phase, pendingWork);

			workList.done(pendingWork);
			workList.pendAll(newWorks);
		}
	}

	public List<Work> processWork(Phase phase, Work work)
	{
		if (work instanceof NodeWork)
			return this.processWork(phase, (NodeWork) work);
		if (work instanceof EdgeWork)
			return this.processWork(phase, (EdgeWork) work);
		throw new RuntimeException("Work type not contemplated");
	}

	protected List<Work> processWork(Phase phase, NodeWork work)
	{
		final List<Work> newWorks = new LinkedList<>();
		final Node initialNode = work.getInitialNode();
		final Node currentNode = work.getCurrentNode();
		final Constraints constraints = work.getConstraints();
		final List<Edge> traversedEdges = work.getTraversedEdges();
		final Set<NodeConstraint> nodeConstraints = constraints.getNodeConstraints();

		final Set<Edge> edges = edg.getEdges(currentNode, sliceDirection);
		edges.removeIf(Edge::isControlFlowEdge);
		if(phase == Phase.SummaryGeneration) {
			edges.removeIf(edge -> edge.getType() == Edge.Type.Exception);
			edges.removeIf(edge -> edge.getType() == Edge.Type.Input ||
									edge.getType() == Edge.Type.Output ||
									edge.getType() == Edge.Type.Call);
		}

		// TRAVERSAL RESTRICTION TODO: Change this restriction to construction time removing structural arcs
		// GENERATOR NODES CONTAIN VALUE EDGES THAT MUST BE TRAVERSED ONLY IF THE GENERATOR NODE IS INCLUDED BY CONTROL
		if (currentNode.getType() == Node.Type.Generator && work.getPreviousEdgeType() != Edge.Type.Control)
				edges.removeIf(edge -> edge.getType() == Edge.Type.Value);

		if (work.getPreviousEdgeType() == Edge.Type.Structural)
			edges.removeIf(edge -> edge.getType() != Edge.Type.Structural);

		for (NodeConstraint nodeConstraint : nodeConstraints)
			nodeConstraint.resolve(phase, edges);

		final Constraints constraintsClone = (Constraints) constraints.clone();
		constraintsClone.clearNodeConstraints();
		for (Edge edge : edges){
			newWorks.add(new EdgeWork(edg, initialNode, edge, traversedEdges, constraintsClone));
		}

		return newWorks;
	}

	protected List<Work> processWork(Phase phase, EdgeWork work)
	{
		final List<Work> newWorks = new LinkedList<>();
		final Node initialNode = work.getInitialNode();
		final Edge currentEdge = work.getCurrentEdge();
		final List<Edge> traversedEdges = work.getTraversedEdges();
		final Node nextNode = sliceDirection == Direction.Backwards ?
				edg.getEdgeSource(currentEdge) : edg.getEdgeTarget(currentEdge);

		// NECESSARY TO CONTROL THE OUTPUT EDGES WITH LET_THROUGH_CONSTRAINTS
		final Edge.Type edgeType = currentEdge.getType();
		if (phase == Phase.Input && edgeType == Edge.Type.Output)
			return newWorks;
		if (phase == Phase.Output && edgeType == Edge.Type.Input)
			return newWorks;
		if (phase == Phase.SummaryGeneration && (edgeType == Edge.Type.Input || edgeType == Edge.Type.Output))
			return newWorks;
		// Do not traverse non-traversable edges
		if (!currentEdge.isTraversable())
			return newWorks;

		int idTo = edg.getEdgeTarget(currentEdge).getId();
		int idFrom = edg.getEdgeSource(currentEdge).getId();

		try
		{
			final Constraints constraints = work.getConstraints();
			final Constraints constraintsClone = (Constraints) constraints.clone();
			final EdgeConstraint constraint = currentEdge.getConstraint();
			final EdgeConstraint topConstraint = constraintsClone.isEdgeConstraintsEmpty() ? null : constraintsClone.peekEdgeConstraint();

			// THIS STATEMENT MAY LAUNCH A StackOverflowError EMPTYING THE STACK (k-limiting 20 elements => Config.MAX_STACK_SIZE = 20;)
			final List<Constraints> newConstraintsList = constraint.resolve(phase, edg, currentEdge, constraintsClone, topConstraint, 0);
			for (Constraints newConstraints : newConstraintsList) {
				List<Edge> traversedParam = new LinkedList<>();
				if (traversedEdges.contains(currentEdge)) { // IF WE TRAVERSE THE SAME EDGE TWICE WHILE TRAVERSING FLOW AND VALUE EDGES...
					List<Edge> loopEdges = work.getTraversedLoop(currentEdge); // 1) WE EXTRACT THE EDGES OF THE LOOP
					boolean isIncreasingLoop = new PDA().isIncreasingLoop(loopEdges); // 2) WE CALL THE PDA TO EVALUATE THE LOOP
					if (isIncreasingLoop) { // 3) IF THE LOOP IS INCREASING...
						// REMOVE STACK (ASTERISK CONSTRAINT) AND CONTINUE TRAVERSAL ADDING THE EDGE TO traversedEdges
						// ACTS AS AN ASTERISK BUT DOES NOT REPLACE THE CONSTRAINT IN THE ARC
						// currentEdge.setVisibleConstraint(AsteriskConstraint.getConstraint());
						traversedParam.add(currentEdge);
						newWorks.add(new NodeWork(initialNode, nextNode, traversedParam, new Constraints(), edgeType));
						// WE CAN OPTIONALLY MODIFY IT TO OPTIMISE FUTURE TRAVERSALS TOO
					} // 4) IF THE LOOP WAS NOT INCREASING RESTART TRAVERSED EDGES (DO NOTHING)
				} else {
					switch (currentEdge.getType()) {
						case Flow: // SUMMARY EDGES MAY GENERATE IT TOO, BUT WE ARE INTRAPROCEDURAL NOW
						case Value:
							if ((constraint instanceof AccessConstraint || !traversedEdges.isEmpty())
									&& !(constraint instanceof LiteralConstraint)) {
								traversedParam.addAll(traversedEdges);
								traversedParam.add(currentEdge);
							}
							break;
						case Input:
						case Output:
							if (!traversedEdges.isEmpty()) {
								traversedParam.addAll(traversedEdges);
								traversedParam.add(currentEdge);
							}
							break;
						default:
							break;
					}
					newWorks.add(new NodeWork(initialNode, nextNode, traversedParam, newConstraints, edgeType));
				}
			}

			return newWorks;
		}
		catch (StackOverflowError e)
		{
			if (!phase.isInstanceof(Phase.Slicing))
				throw new RuntimeException("Constraint situation not contemplated");
			// STACK FULL => EMPTY THE CONSTRAINTS LIST (*)
			newWorks.add(new NodeWork(initialNode, nextNode, new Constraints(), edgeType));
		}

		return newWorks;
	}
}