OnePassConstrainedAlgorithm.java

/*
 * EDG, a library to generate and slice Expression Dependence Graphs.
 * Copyright (c) 2021-2023. David Insa, Carlos Galindo, Sergio Pérez, Josep Silva, Salvador Tamarit.
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU Affero General Public License as
 * published by the Free Software Foundation, either version 3 of the
 * License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU Affero General Public License for more details.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program.  If not, see <https://www.gnu.org/licenses/>.
 */

package edg.slicing;

import edg.constraint.AccessConstraint;
import edg.constraint.Constraints;
import edg.constraint.EdgeConstraint;
import edg.constraint.LiteralConstraint;
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.hasNext())
		{
			final Work pendingWork = workList.removeNext();
			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 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);

		final Constraints constraintsClone = (Constraints) constraints.clone();
		for (Edge edge : edges){
			newWorks.add(new EdgeWork(edg, initialNode, edge, work.getTraversedEdges(), 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 EdgeList 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.isEmpty() ? null : constraintsClone.peek();

			// 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) {
				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 = 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());
						newWorks.add(new NodeWork(initialNode, nextNode, new EdgeList(currentEdge), 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 {
					final EdgeList traversedParam;
					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 = new EdgeList(traversedEdges, currentEdge);
							else
								traversedParam = EdgeList.emptyList();
							break;
						case Input:
						case Output:
							if (!traversedEdges.isEmpty())
								traversedParam = new EdgeList(traversedEdges, currentEdge);
							else
								traversedParam = EdgeList.emptyList();
							break;
						default:
							traversedParam = EdgeList.emptyList();
							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;
	}
}