EKnife.java

/*
 * e-Knife, a program slicing tool for Erlang based on the EDG
 * 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;

import edg.DotFactory;
import edg.EDGFactory;
import edg.PdfFactory;
import edg.graph.EDG;
import edg.graph.Edge;
import edg.graph.LAST;
import edg.graph.Node;
import edg.slicing.*;

import java.io.File;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

public class EKnife
{
	public enum Language { Java, Erlang, Php }

	public static void main(String[] args)
	{
		if (args.length == 0) {
			EKnife.printHelp();
			return;
		}

		final Args arguments = EKnife.processArguments(args);

		if (!arguments.isValid()) {
			EKnife.printHelp();
			System.exit(3);
		}
		EKnife.run(arguments);
	}

	private static Args processArguments(String[] args)
	{
		Args kArgs = new Args();

		for (int argIndex = 0; argIndex < args.length; argIndex++)
		{
			final String arg = args[argIndex];

			switch (arg)
			{
				case "-i": case "--input":
				case "-o": case "--output":
				case "-f": case "--file":
				case "-l": case "--line":
				case "-v": case "--var":
				case "-n": case "--occurrence":
				case "-G": case "--print-graph":
					if (argIndex == args.length - 1) {
						System.out.printf("Parameter %s requires an argument\n", arg);
						printHelp();
						System.exit(1);
					}
			}
			switch (arg)
			{
				case "--help":
					printHelp();
					System.exit(0);
				case "-i": case "--input":
					kArgs.inputPath = args[argIndex + 1];
					break;
				case "-o": case "--output":
					kArgs.outputFile = new File(args[argIndex + 1]);
					break;
				case "-f": case "--file":
					kArgs.file = args[argIndex + 1];
					break;
				case "-l": case "--line":
					kArgs.line = Integer.parseInt(args[argIndex + 1]);
					break;
				case "-v": case "--var":
					kArgs.name = args[argIndex + 1];
					break;
				case "-n": case "--occurrence":
					kArgs.occurrence = Integer.parseInt(args[argIndex + 1]);
					break;
				case "-G": case "--print-graph":
					kArgs.setGraphFile(new File(args[argIndex + 1]));
					break;
			}
		}

		kArgs.completeData();
		return kArgs;
	}
	private static void printHelp()
	{
		String help = "";

		help += "Use the following options:\n";
		help += "  -i,--input  <file/folder>   The file/folder where the source code is\n";
		help += "  -o,--output <file/folder>   The file/folder where the slice will be stored\n";
		help += "  -f,--file   <file>          The file (relative to -i) where the slicing criterion is\n";
		help += "  -l,--line   <num>           The line of the slicing criterion\n";
		help += "  -v,--var    <name>          The name of the slicing criterion (must be a variable)\n";
		help += "  -n,--occurrence <num>       The occurrence of the slicing criterion in that line\n";
		help += "  -G,--print-graph <file.dot> Exports the graph as a dot file\n";
		help += "  -G,--print-graph <file.pdf> Exports the graph as a PDF file\n";
		help += "  --help                      Show this message.\n";

		System.out.print(help);
	}

	private static void run(Args a)
	{
		final LAST last = LASTFactory.createLAST(Language.Erlang, a.inputPath, true);
		final EDG edg = new EDGFactory(last).createEDG();
		final SlicingCriterion slicingCriterion = new SlicingCriterion(a.file, a.line, a.name, a.occurrence);
		final Node SC = edg.getNode(slicingCriterion);
		if (SC == null) {
			System.out.println("Error: the slicing criterion could not be found! " + slicingCriterion);
			System.exit(1);
		}
		final SlicingAlgorithm slicingAlgorithm = new ConstrainedAlgorithm(edg);
		final Set<Node> slice = slicingAlgorithm.slice(SC);
		if (slice.isEmpty()) {
			System.out.println("Warning: no files will be written, as the slice is empty.");
			System.exit(2);
		}
		if (a.graphFile != null) {
			switch (a.graphFormat) {
				case DOT:
					DotFactory.createDot(a.graphFile, edg, SC, slice);
					break;
				case PDF:
					PdfFactory.createPdf(a.graphFile, edg, SC, slice);
					break;
			}
		}
		CodeFactory.createCode(Language.Erlang, a.outputFile, edg, slice);
	}

	private static void timedRun(Args a)
	{
		// CONFIGURE MEASURED DIMENSIONS
		boolean measureGenerationTime = true;
		boolean measureNodes = false;
		boolean performAllSCs = true;
		/*******************************************************/
		/*** MEASUREMENT OF GENERATION TIME (100 executions) ***/
		/*******************************************************/
		int numberOfIterations = 100;

		if (measureGenerationTime) {
	//		double StructuralTime[] = new double[100];
	//		double CFGTime[] = new double[100];
	//		double ValueTime[] = new double[100];
	//		double ControlTime[] = new double[100];
	//		double FlowTime[] = new double[100];

			double totalStructural, totalCFG, totalValue, totalComposite, totalControl, totalFlow;
			totalStructural = totalCFG = totalValue = totalComposite = totalControl = totalFlow = 0.0;

			for (int i = -1; i < numberOfIterations; i++) {

				final LAST last = LASTFactory.createLAST(Language.Erlang, a.inputPath, true);
				final EDG edg = new EDGFactory(last).createEDG();

				if (i == -1)
					continue;

				totalStructural += edg.getGenerationTime().getStructureTime();
				totalCFG += edg.getGenerationTime().getControlFlowTime();
				totalValue += edg.getGenerationTime().getValueTime();
				totalComposite += edg.getGenerationTime().getCompositeTime();
				totalControl += edg.getGenerationTime().getControlTime();
				totalFlow += edg.getGenerationTime().getFlowTime();

//			StructuralTime[i] = edg.getGenerationTime().getStructureTime();
//			CFGTime[i] = edg.getGenerationTime().getControlFlowTime();
//			ValueTime[i] = edg.getGenerationTime().getValueTime();
//			ControlTime[i] = edg.getGenerationTime().getControlTime();
//			FlowTime[i] = edg.getGenerationTime().getFlowTime();
			}

//		double totalStructural, totalCFG, totalValue, totalControl, totalFlow;
//		totalStructural = totalCFG = totalValue = totalControl = totalFlow = 0.0;
//		for (int i = 0; i < 100; i++){
//			totalStructural += StructuralTime[i];
//			totalCFG += CFGTime[i];
//			totalValue += ValueTime[i];
//			totalControl += ControlTime[i];
//			totalFlow += FlowTime[i];
//		}
			// INTRAPROCEDURAL GENERATION TIME
			// TIME MEASSUREMENT:
			printGenerationTime(a.file, numberOfIterations, totalStructural, totalCFG, totalValue,
					totalComposite, totalControl, totalFlow, false);
			printGenerationTime(a.file, numberOfIterations, totalStructural, totalCFG, totalValue,
					totalComposite, totalControl, totalFlow, true);
		}

		final LAST last = LASTFactory.createLAST(Language.Erlang, a.inputPath, true);
		final EDG edg = new EDGFactory(last).createEDG();
		/*****************************/
		/*** MEASUREMENT OF NODES: ***/
		/*****************************/
		if (measureNodes) {
			int SDGNodeCounter = countSDGNodes(edg);
			int EDGNodeCounter = countEDGNodes(edg);

			printNodeCounter(a.file, SDGNodeCounter, EDGNodeCounter);
		}
		/**************************/
		/*** MEASUREMENT OF SCs ***/
		/**************************/
		if (performAllSCs) {

			// SC SELECTION
			List<Node> clauses = edg.getNodes(Node.Type.Clause);
			clauses.removeIf(c -> edg.getParent(c).getType() != Node.Type.Routine);

			printTitle("/Users/serperu/Desktop/SlicerOutput/Times/slicingStatistics.txt", a.file);

			for (Node clause : clauses) {
				List<Node> descendants = edg.getDescendants(clause);
				descendants.add(clause);

				List<Node> resultNodes = new LinkedList<>();
				List<Node> nonResultNodes = new LinkedList<>();

				for (Node n : descendants)
					if (n.getType() == Node.Type.Result) {
						if (edg.getNodeFromRes(n).getType() != Node.Type.Callee)
							resultNodes.add(n);
					} else
						nonResultNodes.add(n);
				nonResultNodes.add(clause);
				resultNodes.add(edg.getResFromNode(clause));


				// IGNORE FUNCTIONS WITHOUT COMPOSITE STRUCTURES
				if (nonResultNodes.stream()
						.noneMatch(
								n -> { if (n.getType() == Node.Type.DataConstructor)
											return true;
										if (n.getType() == Node.Type.List)
											if (edg.getChildren(n).size() != 0 || edg.getParent(n).getType() == Node.Type.List)
												return true;
										return false;})) {
					System.out.println("File Name: " + a.file);
					int functionArity = edg.getChildrenNonResult(edg.getChild(clause, Node.Type.Parameters)).size();
					System.out.println("Function " + edg.getParent(clause).getName() + "/" + functionArity + " has no valid slicing criteria.");
					continue;
				}

				/* FILTER SC NODES BY A CRITERION (REMOVE LITERALS) */
				resultNodes.removeIf(n -> edg.getNodeFromRes(n).getType() == Node.Type.Literal);

				/* SPECIFIC FILTER FOR BENCH1.ERL */
				// TODO: Detect and generalise the scenario
				if (a.file.equals("bench1.erl"))
					resultNodes.removeIf(sc -> edg.getAncestor(sc, Node.Type.Equality) != null &&
							edg.getChild(
									edg.getAncestor(sc, Node.Type.Equality), Node.Type.Pattern)
									.getName().equals("Database"));
				/* *********** */

				SlicingCriterionState[] allCriteriaStandard = new SlicingCriterionState[resultNodes.size()];
				SlicingCriterionState[] allCriteriaConstrained = new SlicingCriterionState[resultNodes.size()];

				// CONFIGURE MEASURED DIMENSIONS
				boolean measureSlicingPerformance = false;
				boolean measureSlicingTime = true;

				final SlicingAlgorithm standardAlgorithm = new AdaptedStandardAlgorithm(edg);
				final SlicingAlgorithm constrainedAlgorithm = new ConstrainedAlgorithm(edg);

				int scCounter = 0;
				int scConstrainedImprovements = 0;

				for (Node SC : resultNodes) {
					// INITIALIZATIONS
						// PERFORMANCE
					double standardSlicePercentage = 0.0;
					double constrainedSlicePercentage = 0.0;
						// TIME
					double standardTimeMean = 0.0;
					double constrainedTimeMean = 0.0;

					// MEASURE TIME FOR EACH SC
					if (measureSlicingTime) {
						for (int j = -1; j < numberOfIterations; j++) {
							long initialStandardTime = System.nanoTime();
							standardAlgorithm.slice(SC);
							long finalStandardTime = System.nanoTime();

							long initialConstrainedTime = System.nanoTime();
							constrainedAlgorithm.slice(SC);
							long finalConstrainedTime = System.nanoTime();

							if (j == -1)
								continue;

							standardTimeMean += (finalStandardTime - initialStandardTime) / (numberOfIterations * 1000000.0);
							constrainedTimeMean += (finalConstrainedTime - initialConstrainedTime) / (numberOfIterations * 1000000.0);
						}
						standardTimeMean /= numberOfIterations;
						constrainedTimeMean /= numberOfIterations;
					}

					// MEASURE PERFORMARNCE
					final Set<Node> standardSlice = standardAlgorithm.slice(SC);
					final Set<Node> constrainedSlice = constrainedAlgorithm.slice(SC);


					if (measureSlicingPerformance) {
						standardSlice.removeIf(n -> n.getType() == Node.Type.Result ||
								n.getType() == Node.Type.Routine || n.getType() == Node.Type.Module
								|| n.getType() == Node.Type.Root);
						standardSlicePercentage = standardSlice.size() * 100.0 / nonResultNodes.size();

						constrainedSlice.removeIf(n -> n.getType() == Node.Type.Result ||
								n.getType() == Node.Type.Routine || n.getType() == Node.Type.Module
								|| n.getType() == Node.Type.Root);
						constrainedSlicePercentage = constrainedSlice.size() * 100.0 / nonResultNodes.size();

						if (constrainedSlice.size() < standardSlice.size())
							scConstrainedImprovements++;

						if (standardSlicePercentage < constrainedSlicePercentage)
							throw new IllegalStateException("The SDG cannot be more precise than the EDG");

					}
					allCriteriaStandard[scCounter] = new SlicingCriterionState(standardSlicePercentage, standardTimeMean);
					allCriteriaConstrained[scCounter] = new SlicingCriterionState(constrainedSlicePercentage, constrainedTimeMean);
					scCounter++;
				}
				int arity = edg.getChildrenNonResult(edg.getChild(clause, Node.Type.Parameters)).size();
				printSlicingResults(edg.getParent(clause).getName() + "/" + arity,
					resultNodes.size(), allCriteriaStandard, allCriteriaConstrained,
						scConstrainedImprovements, measureSlicingPerformance, measureSlicingTime);
			}
		}
//		DotFactory.createDot(new File("/Users/serperu/Desktop/SlicerOutput/graphSliced.dot"), edg, SC, slice, edgeFlags);
//		CodeFactory.createCode(Language.Erlang, a.outputFile, edg, slice);
	}

	public static int countSDGNodes(EDG edg) {
		Node root = edg.getRootNode();
		return countSDGNodes(edg, root);
	}

	public static int countSDGNodes(EDG edg, Node node) {
		int counter = 1;
		List<Node> children = edg.getChildren(node);
		for (Node child : children) {
			if (child.getType() == Node.Type.Result)
				continue;
			if (child.getType() == Node.Type.List ||child.getType() == Node.Type.DataConstructor)
				counter++;
			else {
				counter += countSDGNodes(edg, child);
			}
		}
		return counter;
	}

	public static int countEDGNodes(EDG edg) {
		Set<Node> nodes = new HashSet<>();
		nodes.addAll(edg.vertexSet());
		nodes.removeIf(n -> n.getType() == Node.Type.Result);
		return nodes.size();
	}

	public static void printGenerationTime(String programName, int numberOfIterations, double totalStructural,
										   double totalCFG, double totalValue, double totalComposite,
										   double totalControl, double totalFlow, boolean isEDG) {
		FileWriter timeFileWriter;
		PrintWriter timeWriter = null;
		try {
			String graphName = isEDG ? "EDG" : "SDG";
			timeFileWriter = new FileWriter("/Users/serperu/Desktop/SlicerOutput/Times/generationTime"+graphName+".txt", true);
			timeWriter = new PrintWriter(timeFileWriter);
			timeWriter.println("---------------------------");
			timeWriter.println("-------- "+graphName+" TIME ---------");
			timeWriter.println("---------------------------");
			timeWriter.println("Program Name: " + programName);
			timeWriter.println("---------------------------");
//			timeWriter.println("StructuralTime: " + totalStructural  / StructuralTime.length + " ms");
//			timeWriter.println("ControlFlowTime: " + totalCFG / CFGTime.length + " ms");
//			timeWriter.println("ValueTime: " + totalValue / ValueTime.length + " ms");
//			timeWriter.println("ControlTime: " + totalControl / ControlTime.length + " ms");
//			timeWriter.println("FlowTime: " + totalFlow / FlowTime.length + " ms");
//			double TotalTime = (totalStructural + totalCFG + totalValue + totalControl + totalFlow) / StructuralTime.length;
//			timeWriter.println("TOTAL TIME: " + TotalTime + " ms\n");
			timeWriter.println("StructuralTime: " + totalStructural / numberOfIterations + " ms");
			timeWriter.println("ControlFlowTime: " + totalCFG / numberOfIterations + " ms");
			if (!isEDG)
				totalValue -= totalComposite; // SDG Time ignores Composite Structures Generation
			timeWriter.println("ValueTime: " + totalValue / numberOfIterations + " ms");
			timeWriter.println("ControlTime: " + totalControl / numberOfIterations + " ms");
			timeWriter.println("FlowTime: " + totalFlow / numberOfIterations + " ms");
			double TotalTime = (totalStructural + totalCFG + totalValue + totalControl + totalFlow) / numberOfIterations;
			timeWriter.println("TOTAL TIME: " + TotalTime + " ms\n");

		} catch (IOException e) {
			System.out.println("FILE NOT FOUND ERROR");
		} finally {
			if (timeWriter != null)
				timeWriter.close();
		}
	}

	public static void printNodeCounter(String programName, int SDGNodes, int EDGNodes) {
		FileWriter timeFileWriter;
		PrintWriter timeWriter = null;
		try {
			timeFileWriter = new FileWriter("/Users/serperu/Desktop/SlicerOutput/Times/programSizes.txt", true);
			timeWriter = new PrintWriter(timeFileWriter);
			timeWriter.println("---------------------------");
			timeWriter.println("Program Name: " + programName);
			timeWriter.println("---------------------------");
			timeWriter.println(" SDG Nodes: " + SDGNodes);
			timeWriter.println(" EDG Nodes: " + EDGNodes + "\n");
		} catch (IOException e) {
			System.out.println("FILE NOT FOUND ERROR");
		} finally {
			if (timeWriter != null)
				timeWriter.close();
		}
	}

	public static void printTitle(String outputFile, String fileName) {
		FileWriter timeFileWriter;
		PrintWriter timeWriter = null;
		try {
			timeFileWriter = new FileWriter(outputFile, true);
			timeWriter = new PrintWriter(timeFileWriter);
			timeWriter.println("*******************************");
			timeWriter.println("* Program Name: " + fileName + " *");
			timeWriter.println("*******************************");
		} catch (IOException e) {
			System.out.println("FILE NOT FOUND ERROR");
		} finally {
			if (timeWriter != null)
				timeWriter.close();
		}
	}

	public static void printSlicingResults(String funName, int numberOfSCs, SlicingCriterionState[] standard,
										   SlicingCriterionState[] constrained, int improvements, boolean performance,
										   boolean time) {

		FileWriter timeFileWriter;
		PrintWriter timeWriter = null;
		try {
			timeFileWriter = new FileWriter("/Users/serperu/Desktop/SlicerOutput/Times/slicingStatistics.txt", true);
			timeWriter = new PrintWriter(timeFileWriter);
			timeWriter.println("\t++++++++++++++++++++++++++++");
			timeWriter.println("\t+ Function Name: " + funName + " +");
			timeWriter.println("\t++++++++++++++++++++++++++++");
			timeWriter.println("\t Number of SCs: " + numberOfSCs);

			double standardAlgorithmAvgPerformance = 0.0;
			double standardAlgorithmAvgTime = 0.0;

			for (int k = 0; k < numberOfSCs; k++) {
				standardAlgorithmAvgPerformance += standard[k].getPerformance();
				standardAlgorithmAvgTime += standard[k].getTime();
			}
			timeWriter.println("\t\t----------------------");
			timeWriter.println("\t\t- Standard Algorithm -");
			timeWriter.println("\t\t----------------------");
			if (performance)
				timeWriter.println("\t\t Average Performance: " + (standardAlgorithmAvgPerformance / numberOfSCs) + " % \n");
			if (time)
				timeWriter.println("\t\t Average Time: " + (standardAlgorithmAvgTime / numberOfSCs) + " ms \n");

			double constrainedAlgorithmAvgPerformance = 0.0;
			double constrainedAlgorithmAvgTime = 0.0;

			for (int k = 0; k < numberOfSCs; k++) {
				constrainedAlgorithmAvgPerformance += constrained[k].getPerformance();
				constrainedAlgorithmAvgTime += constrained[k].getTime();
			}
			timeWriter.println("\t\t-------------------------");
			timeWriter.println("\t\t- Constrained Algorithm -");
			timeWriter.println("\t\t-------------------------");
			if (performance) {
				timeWriter.println("\t\t Average Performance: " + (constrainedAlgorithmAvgPerformance / numberOfSCs) + " % \n");
				timeWriter.println("\t\t Obtained smaller slices: " + improvements + " times\n");
			}
			if (time)
				timeWriter.println("\t\t Average Time: " + (constrainedAlgorithmAvgTime / numberOfSCs) +  " ms\n");

		} catch (IOException e) {
			System.out.println("FILE NOT FOUND ERROR");
		} finally {
			if (timeWriter != null)
				timeWriter.close();
		}
	}

	static class Args {
		enum GraphFormat { PDF, DOT }

		String inputPath;
		File outputFile;
		String file;
		int line;
		String name;
		int occurrence = 1;
		File graphFile;
		GraphFormat graphFormat;


		void setGraphFile(File graphFile) {
			if (graphFile.getName().endsWith(".dot"))
				graphFormat = GraphFormat.DOT;
			else if (graphFile.getName().endsWith(".pdf"))
				graphFormat = GraphFormat.PDF;
			else {
				System.out.println("The graph file must end in .dot or .pdf, you set it to " + graphFile);
				System.exit(1);
			}
			this.graphFile = graphFile;
		}

		void completeData() {
			if (file == null && inputPath != null && new File(inputPath).isFile())
				file = new File(inputPath).getName();
		}

		boolean isValid() {
			List<String> errors = new LinkedList<>();
			if (inputPath == null)
				errors.add("You must specify a file to analyze with '-i'.");
			else if (!new File(inputPath).exists())
				errors.add("The input file you've specified does not exist or isn't readable(" + inputPath + ").");
			else if (file == null)
				errors.add("The input file is a folder, so you must specify a the file that contains the slicing criterion with '-f'.");
			if (outputFile == null)
				errors.add("You must specify a location for the output with '-o'.");
			else if (!outputFile.exists() && !outputFile.getAbsoluteFile().getParentFile().isDirectory())
				errors.add("The output file's parent folder does not exist, or the output folder does not exist.");
			if (line <= 0)
				errors.add("You must specify a line number greater than 0 with '-l'.");
			if (name == null || name.isEmpty())
				errors.add("You must specify a valid variable name with '-v'.");
			if (occurrence <= 0)
				errors.add("You must specify an occurrence greater than 0 with '-n'.");
			for (String error : errors)
				System.out.println(error);
			return errors.isEmpty();
		}
	}

	private static class SlicingCriterionState{
		private final double slicingPerformance;
		private final double slicingTime;

		public SlicingCriterionState(double performance, double time) {
			slicingPerformance = performance;
			slicingTime = time;
		}
		public double getPerformance() { return this.slicingPerformance; }
		public double getTime() { return this.slicingTime; }

	}
}