ValueEdgeGenerator.java

/*
 * EDG, a library to generate and slice Expression Dependence Graphs.
 * Copyright (c) 2021. David Insa, 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 eknife.erlang;

import java.util.List;
import java.util.Set;

import edg.constraint.*;
import edg.graph.Edge;
import edg.graph.LAST;
import edg.graph.Node;

public class ValueEdgeGenerator {
	
	protected final LAST last;
	
	public ValueEdgeGenerator(LAST last)
	{
		this.last = last;
	}

	public void generate()
	{
		this.generateEqualityEdges();
		this.generateDataConstructorEdges();
		this.generateListEdges();
		this.generateOperationEdges();
		this.generateSwitchEdges();
		this.generateListComprehensionEdges();
		this.generateGeneratorEdges();
		this.generateRoutineCallEdges();
		this.generateReturnEdges();
		this.generateRoutineEdges();
	}

	private void generateEqualityEdges()
	{
		final List<Node> equalities = this.last.getNodes(Node.Type.Equality);

		for (Node equality : equalities)
		{
			final Node pattern = this.last.getChild(equality, Node.Type.Pattern);
			final Node expression = this.last.getChild(equality, Node.Type.Value);

			this.last.addEdge(expression, equality, Edge.Type.Value);
			this.last.addEdge(equality, pattern, Edge.Type.Value);
		}
	}
	private void generateDataConstructorEdges()
	{
		final List<Node> dataConstructors = this.last.getNodes(Node.Type.DataConstructor);

		for (Node dataConstructor : dataConstructors)
		{
			final boolean isPatternZone = this.last.isPatternZone(dataConstructor);
			final AccessConstraint.Operation operation = isPatternZone ? AccessConstraint.Operation.Add : AccessConstraint.Operation.Remove;
			final List<Node> dataConstructorChildren = this.last.getChildren(dataConstructor);

			for (int childIndex = 0; childIndex < dataConstructorChildren.size(); childIndex++) {
				final Node dataConstructorChild = dataConstructorChildren.get(childIndex);
				final Node from = isPatternZone ? dataConstructor : dataConstructorChild;
				final Node to = isPatternZone ? dataConstructorChild : dataConstructor;
				final DataConstructorConstraint constraint = new DataConstructorConstraint(operation, childIndex + "");
				this.last.addEdge(from, to, Edge.Type.Value, constraint);

				if (!isPatternZone){
					switch(dataConstructorChild.getType()){
						case List:
							ListConstraint lc = new ListConstraint(AccessConstraint.Operation.Remove, ListConstraint.Position.S);
							this.last.addEdge(dataConstructorChild, dataConstructor, Edge.Type.ValueStructure, lc);
							break;
						case DataConstructor:
							DataConstructorConstraint dc = new DataConstructorConstraint(AccessConstraint.Operation.Remove, "S");
							this.last.addEdge(dataConstructorChild, dataConstructor, Edge.Type.ValueStructure, dc);
							break;
//						case Literal:
//							LiteralConstraint litc = new LiteralConstraint(AccessConstraint.Operation.Remove);
//							this.last.addEdge(dataConstructorChild, dataConstructor, Edge.Type.ValueStructure, litc);
//							break;
						default:
							break;
					}
				}
			}
		}
	}
	private void generateListEdges()
	{
		final List<Node> lists = this.last.getNodes(Node.Type.List);

		for (Node list : lists)
		{
			final boolean isPatternZone = this.last.isPatternZone(list);
			final AccessConstraint.Operation operation = isPatternZone ? AccessConstraint.Operation.Add : AccessConstraint.Operation.Remove;

			if (this.last.getChildren(list).isEmpty())
				continue;

			final Node head = this.last.getChild(list, Node.Type.Value);
			final ListConstraint headConstraint = new ListConstraint(operation, ListConstraint.Position.H);

			final Node tail = this.last.getChild(list, Node.Type.List);
			final ListConstraint tailConstraint = new ListConstraint(operation, ListConstraint.Position.T);

			if (isPatternZone) {
				this.last.addEdge(list, head, Edge.Type.Value, headConstraint);
				this.last.addEdge(list, tail, Edge.Type.Value, tailConstraint);
			} else {
				this.last.addEdge(head, list, Edge.Type.Value, headConstraint);
				this.last.addEdge(tail, list, Edge.Type.Value, tailConstraint);
			}
		}
	}
//	private void generateDataConstructorAccessEdges()
//	{
//		final List<Node> dataConstructorAccesses = this.last.getNodes(Node.Type.DataConstructorAccess);
//
//		for (Node dataConstructorAccess : dataConstructorAccesses)
//		{
//			final Node dataConstructorAccessResult = this.last.getSibling(dataConstructorAccess, Node.Type.Result);
//			final Node dataConstructor = this.last.getChild(dataConstructorAccess, 0);
//			final Node dataConstructorResult = this.last.getSibling(dataConstructor, Node.Type.Result);
//			final Node indexExpression = this.last.getChild(dataConstructorAccess, 1);
//			final Node index = this.last.getChild(indexExpression, 0);
//			final Node indexResult = this.last.getSibling(index, Node.Type.Result);
//			final String indexValue = index.getType() == Node.Type.Literal ? index.getName() : "*";
//			final EdgeConstraint constraint = new DataConstructorConstraint(AccessConstraint.Operation.Add, indexValue);
//
//			this.last.addEdge(dataConstructorResult, dataConstructorAccessResult, Edge.Type.Value, constraint);
//			this.last.addEdge(indexResult, dataConstructorAccessResult, Edge.Type.Value, AsteriskConstraint.getConstraint());
//		}
//	}
	private void generateOperationEdges()
	{
		final List<Node> operations = this.last.getNodes(Node.Type.Operation);
		for (Node operation : operations)
		{
			final List<Node> operators = this.last.getChildren(operation);
			for (Node operator : operators)
				this.last.addEdge(operator, operation, Edge.Type.Value);
		}
	}
	private void generateSwitchEdges()
	{
		final List<Node> switches = this.last.getNodes(Node.Type.Switch);

		for (Node _switch : switches)
		{
			final Node selectorNode = this.last.getChild(_switch, Node.Type.Selector);
			final Node casesNode = this.last.getChild(_switch, Node.Type.Cases);
			final List<Node> cases = this.last.getChildren(casesNode);

			for (Node _case : cases)
			{
				final Node selectableNode = this.last.getChild(_case, Node.Type.Selectable);

				final Node selector = this.last.getChild(selectorNode, Node.Type.Value);
				if (selector != null) {
					final Node selectable = this.last.getChild(selectableNode, Node.Type.Value);
					this.last.addEdge(selector, selectable, Edge.Type.Value, EmptyConstraint.getConstraint());
				}
			}
		}
	}

	private boolean isCFGReached(Node node) {
		Set<Edge> outgoingCFGEdges = this.last.getEdges(node, LAST.Direction.Forwards);
		outgoingCFGEdges.removeIf(e -> e.getType() != Edge.Type.ControlFlow);

		return outgoingCFGEdges.size() > 0;
	}

	private void generateListComprehensionEdges()
	{
		final List<Node> listComprehensionNodes = this.last.getNodes(Node.Type.ListComprehension);
		final EdgeConstraint negativeConstraint = new ListComprehensionConstraint(ListComprehensionConstraint.Operation.Remove);
		for (Node listComprehensionNode : listComprehensionNodes)
		{
			final Node valueNode = this.last.getChild(listComprehensionNode, Node.Type.Value);
			final Node value = this.last.getChild(valueNode, Node.Type.Value);
			this.last.addEdge(value, listComprehensionNode, Edge.Type.Value, negativeConstraint);
		}
	}

	private void generateGeneratorEdges()
	{
		final List<Node> generators = this.last.getNodes(Node.Type.Generator);
		final EdgeConstraint positiveConstraint = new ListComprehensionConstraint(ListComprehensionConstraint.Operation.Add);
		final EdgeConstraint listStructureConstraint = new ListConstraint(AccessConstraint.Operation.Add, ListConstraint.Position.S);
		for (Node generator : generators)
		{
			final Node pattern = this.last.getChild(generator, Node.Type.Variable);
			final Node expression = this.last.getChild(generator, Node.Type.Iterator);
			this.generateGeneratorPatternStructureEdges(generator, pattern);
			this.last.addEdge(expression, generator, Edge.Type.Value, listStructureConstraint);
			this.last.addEdge(expression, pattern, Edge.Type.Value, positiveConstraint);
		}
	}

	private void generateGeneratorPatternStructureEdges(Node parent, Node pattern){
		switch(pattern.getType()){
			case List:
				ListConstraint lc = new ListConstraint(AccessConstraint.Operation.Add, ListConstraint.Position.S);
				this.last.addEdge(pattern, parent, Edge.Type.ValueStructure, lc);
				generateGeneratorPatternStructureEdges(pattern);
				break;
			case DataConstructor:
				DataConstructorConstraint dc = new DataConstructorConstraint(AccessConstraint.Operation.Add, "S");
				this.last.addEdge(pattern, parent, Edge.Type.ValueStructure, dc);
				generateGeneratorPatternStructureEdges(pattern);
				break;
			case Literal:
				if (parent.getType() == Node.Type.Generator)
					this.last.addEdge(pattern, parent, Edge.Type.ValueStructure, EmptyConstraint.getConstraint());
				else {
					final Node genNode = this.last.getAncestor(parent, Node.Type.Generator);
					this.last.addEdge(pattern, genNode, Edge.Type.Value, EmptyConstraint.getConstraint());
				}
				// generateGeneratorPatternStructureEdges(pattern);
				break;
			default:
				break;
		}
	}

	private void generateGeneratorPatternStructureEdges(Node pattern) {
		List<Node> children = last.getChildrenNonResult(pattern);
		boolean allChildrenLeaves = true;
		for (Node child : children)
			if (child.getType() == Node.Type.DataConstructor || child.getType() == Node.Type.List
					|| child.getType() == Node.Type.Literal) {
				allChildrenLeaves = false;
				this.generateGeneratorPatternStructureEdges(pattern, child);
			}
		if (allChildrenLeaves) {
			Node generator = this.last.getAncestor(pattern, Node.Type.Generator);
			Node  variableIt = this.last.getChild(generator, Node.Type.Iterator);
			final EdgeConstraint positiveConstraint = new ListComprehensionConstraint(ListComprehensionConstraint.Operation.Add);
			this.last.addEdge(variableIt, pattern, Edge.Type.ValueStructure, positiveConstraint);
		}
	}

	private void generateRoutineCallEdges()
	{
		final List<Node> calls = this.last.getNodes(Node.Type.Call);

		for (Node call : calls)
		{
			final Node callee = this.last.getChild(call, Node.Type.Callee);
			this.last.addEdge(callee, call, Edge.Type.Value, AsteriskConstraint.getConstraint());

			final Node scopeNode = this.last.getChild(callee, Node.Type.Scope);
			if (!this.last.getChildren(scopeNode).isEmpty())
			{
				final Node scope = this.last.getChild(scopeNode, Node.Type.Value);
				this.last.addEdge(scope, callee, Edge.Type.Value, EmptyConstraint.getConstraint());
			}

			final Node nameNode = this.last.getChild(callee, Node.Type.Name);
			final Node name = this.last.getChild(nameNode, Node.Type.Value);
			this.last.addEdge(name, callee, Edge.Type.Value, EmptyConstraint.getConstraint());
		}
	}
	private void generateReturnEdges()
	{
		final List<Node> returns = this.last.getNodes(Node.Type.Return);

		for (Node returnNode : returns)
		{
			if (this.last.getChildren(returnNode).isEmpty())
				continue;

			if (!isCFGReached(returnNode))
				continue;

			final Node returnExpr = this.last.getChild(returnNode, Node.Type.Value);
			final String returnText = returnNode.getName();
			final int dstId = Integer.parseInt(returnText.substring(returnText.lastIndexOf(" ") + 1));
			final Node dstNode = this.last.getNode(dstId);
			this.last.addEdge(returnExpr, dstNode, Edge.Type.Value, EmptyConstraint.getConstraint());
		}
	}
	private void generateRoutineEdges()
	{
		final List<Node> routines = this.last.getNodes(Node.Type.Routine);
		routines.addAll(this.last.getNodes(Node.Type.AnonymousRoutine));

		for (Node routine : routines)
		{
//			final Node routineParent = this.last.getParent(routine);
//			final Node.Type routineParentType = routineParent.getType();
//			if (routineParentType == Node.Type.Module)
//				continue;
			final List<Node> clauses = this.last.getChildren(routine);
			for (Node clause : clauses)
				this.last.addEdge(clause, routine, Edge.Type.Value, EmptyConstraint.getConstraint());
		}
	}
}