SummaryEdgeGenerator.java

package edg.edge;

import java.util.*;

import edg.constraint.*;
import edg.graph.*;
import edg.slicing.ConstrainedAlgorithm;
import edg.slicing.Phase;
import edg.graph.LAST.Direction;
import edg.work.NodeWork;
import edg.work.Work;
import edg.work.WorkList;

public class SummaryEdgeGenerator extends EdgeGenerator
{
	public SummaryEdgeGenerator(EDG edg)
	{
		super(edg);
	}

	public void generate()
	{
		this.generateExternalSummaryEdges();
		this.generateInternalSummaryEdges();
	}

	/* ********************************** */
	/* ************ External ************ */
	/* ********************************** */
	private void generateExternalSummaryEdges()
	{
		final List<Node> calls = edg.getNodes(Node.Type.Call);

		for (Node call : calls)
		{
			final Node callee = edg.getChild(call, Node.Type.Callee);
			final Node calleeResult = edg.getResFromNode(callee);
			final Set<Edge> callEdges = edg.getEdges(calleeResult, LAST.Direction.Forwards, Edge.Type.Call);
			if (!callEdges.isEmpty())
				continue;

			final Node callResult = edg.getResFromNode(call);
			final Node argumentsNode = edg.getChild(call, Node.Type.Arguments);
			final List<Node> arguments = edg.getChildren(argumentsNode);
			arguments.removeIf(n -> n.getType() == Node.Type.Result);

			for (Node argument : arguments)
			{
				final Node argumentResult = edg.getResFromNode(argument);
				this.edg.addEdge(argumentResult, callResult, new Edge(Edge.Type.Summary, AsteriskConstraint.getConstraint()));
			}
		}
	}

	/* ********************************** */
	/* ************ Internal ************ */
	/* ********************************** */
	private void generateInternalSummaryEdges()
	{
		final List<Work> initialWorks = this.getInitialWorks();
		final WorkList workList = new WorkList(initialWorks);
		final ConstrainedAlgorithm slicingAlgorithm = new ConstrainedAlgorithm(edg);

		while (workList.hasMore())
		{
			final Work work = workList.next();
			final Node initialNode = work.getInitialNode();
			final Constraints constraints = work.getConstraints();
			boolean isFormalIn = false;
			
			if (work instanceof NodeWork)
			{
				final NodeWork nodeWork = (NodeWork) work;
				final Node currentNode = nodeWork.getCurrentNode();

				// The current node is the clause node of the initial node or the routine node of this clause result
				if (currentNode == edg.getNodeFromRes(initialNode) || currentNode == edg.getParent(initialNode))
					continue;

				// This avoids the multiple evaluation of the same expressions which are in a circular dependency
				// WARNING: This may lead to incomplete grammars due to lack of looped constraints
				if (workList.getDoneNodes().contains(currentNode) && edg.getNodeFromRes(initialNode).getType() != Node.Type.Clause)
					continue;

				if (isFormalIn = this.isFormalIn(currentNode, initialNode))
				{
					final List<Node> nodesToContinue = this.createSummaryEdges(currentNode, constraints);
					this.rependWorks(workList, nodesToContinue);
				}
			}
			workList.done(work);
			if (isFormalIn)
				continue;

			final List<Work> newWorks = slicingAlgorithm.processWork(Phase.SummaryGeneration, work);
			workList.pendAll(newWorks);
		}
	}
	private List<Work> getInitialWorks()
	{
		final List<Work> workList = new LinkedList<>();
		final List<Node> routines = edg.getNodes(Node.Type.Routine);
		routines.addAll(edg.getNodes(Node.Type.AnonymousRoutine));

		for (Node routine : routines)
		{
			final List<Node> clauses = edg.getChildrenNonResult(routine);
			for (Node clause : clauses)
			{
				Set<Edge> incomingEdges = edg.getEdges(clause,Direction.Backwards);
				incomingEdges.removeIf(e -> e.getType() != Edge.Type.Call);
				if (incomingEdges.isEmpty())
					continue;

				// Summary Edges for the result node
				final Node clauseResult = edg.getResFromNode(clause);
				workList.add(new NodeWork(clauseResult, clauseResult, new Constraints()));
			}
		}
		return workList;
	}
	private boolean isFormalIn(Node node, Node formalOutNode) // formalOutNode is only ClauseResult in Erlang
	{
		final Node parent = edg.getParent(node);
		if (parent == null)
			return false;

		// We reach a parameters node that does not correspond to the formalOut (anonymous functions)
		if (parent.getType() == Node.Type.Parameters) {
			final Node clause = edg.getParent(parent);
			final Node formalInClauseResult = edg.getResFromNode(clause);
			return formalInClauseResult == formalOutNode;
		}

		return false;
	}
	private List<Node> createSummaryEdges(Node formalIn, Constraints constraints)
	{
		final Grammar grammar = this.edg.getGrammar();
		final GrammarConstraint grammarConstraint = new GrammarConstraint(grammar, formalIn);
		boolean isNewGrammarTerm = grammar.isNewGrammarTerm(grammarConstraint);
		if (!isLeftRecursiveGrammar(grammarConstraint, constraints))
			this.edg.addProduction(grammarConstraint, constraints);

		final List<Node> nodesToContinue = new LinkedList<>();
		if (!isNewGrammarTerm)
			return nodesToContinue;

		final List<Node> inputs = edg.getInputs(formalIn, Direction.Backwards);
		for (Node input : inputs)
		{
			final Node call = edg.getAncestor(input, Node.Type.Call);
			if (call == null)
				continue;

			final Node callResult = edg.getResFromNode(call);
			this.edg.addEdge(input, callResult, new Edge(Edge.Type.Summary, grammarConstraint));
			nodesToContinue.add(callResult);
		}

		return nodesToContinue;
	}
	private void rependWorks(WorkList workList, List<Node> nodesToContinue)
	{
		for (Node nodeToContinue : nodesToContinue)
		{
			final String id = nodeToContinue.getId() + "";
			workList.repend(id);
		}
	}

	private boolean isLeftRecursiveGrammar(GrammarConstraint grammarConstraint, Constraints constraints)
	{
		if (constraints.getEdgeConstraints().isEmpty())
			return false;

		String grammarId = grammarConstraint.getRefNode().getId() + "";
		String stackBottomTerm = constraints.getEdgeConstraints().firstElement().toString();
		return grammarId.equals(stackBottomTerm);
	}
}