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.FileWriter;
import java.io.IOException;
import java.io.PrintWriter;
import java.util.*;
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}

	// TODO: OUTPUT FILES PATH

	// Graph Generation Time
	public static final String baseDir = "/Users/serperu/Desktop/SlicerOutput/JSS_Empirical_Evaluation/";
	public static final String outputTimeFolder = baseDir + "Times/";
	public static final String sliceTimeFolder = outputTimeFolder + "Slices/";
	public static final String outputSliceGenerationFolder = baseDir + "Slices/";


	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);

	}

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

		final Args arguments = EKnife.processArguments(args);

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

		EKnife.sliceGenerationRun(arguments, setName);
	}

	public static void timedRun(String[] args, String setName) {

		if (args.length == 0) {
			EKnife.printHelp();
			return;
		}

		final Args arguments = EKnife.processArguments(args);

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

		EKnife.timedRun(arguments,setName);
//		EKnife.SCCounter(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 AdaptedStandardAlgorithm(edg);
		final SlicingAlgorithm slicingAlgorithm = new OnePassConstrainedAlgorithm(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);
	}

	/**
	 * Executes and measures time for graph generation and slicing according to measured dimensions
	 */
	private static void timedRun(Args a, String setName) {
		// CONFIGURE MEASURED DIMENSIONS
		boolean measureGenerationTime = true;
		boolean performAllSCs = true;
		/* ***************************************************** */
		/* ** MEASUREMENT OF GENERATION TIME (100 executions) ** */
		/* ***************************************************** */
		int numberOfIterationsGen = 2;
		int numberOfIterationsSlice = 5;

		// GET MODULE NAME:
		String moduleName = a.inputPath.lastIndexOf(File.separator) != -1 ?
				a.inputPath.substring(a.inputPath.lastIndexOf("/") + 1) : a.inputPath;
		moduleName = moduleName.lastIndexOf(".") != -1 ?
				moduleName.substring(0, moduleName.lastIndexOf(".")) : moduleName;

		if (measureGenerationTime) {
			double[] StructuralTime = new double[numberOfIterationsGen];
			double[] CFGTime = new double[numberOfIterationsGen];
			double[] ValueTime = new double[numberOfIterationsGen];
			double[] CompositeTime = new double[numberOfIterationsGen];
			double[] ControlTime = new double[numberOfIterationsGen];
			double[] FlowTime = new double[numberOfIterationsGen];
			double[] IPTime = new double[numberOfIterationsGen];

			double[] standardTime = new double[numberOfIterationsGen];
			double[] constrainedTime = new double[numberOfIterationsGen];

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

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

				if (i == -1)
					continue;

				StructuralTime[i] = edg.getGenerationTime().getStructureTime();
				CFGTime[i] = edg.getGenerationTime().getControlFlowTime();
				ValueTime[i] = edg.getGenerationTime().getValueTime();
				CompositeTime[i] = edg.getGenerationTime().getCompositeTime();
				ControlTime[i] = edg.getGenerationTime().getControlTime();
				FlowTime[i] = edg.getGenerationTime().getFlowTime();
				IPTime[i] = edg.getGenerationTime().getInterproceduralTime();
				standardTime[i] = StructuralTime[i] + CFGTime[i] + ValueTime[i] - CompositeTime[i]
						+ ControlTime[i] + FlowTime[i] + IPTime[i];
				constrainedTime[i] = StructuralTime[i] + CFGTime[i] + ValueTime[i]
						+ ControlTime[i] + FlowTime[i] + IPTime[i];
				// printArray("/Users/serperu/Desktop/SlicerOutput/Times/ArrayContent.txt",constrainedTime);
			}

			// Print RESULTS:
			try {

				new File(outputTimeFolder).mkdirs();

				File txtSDG = new File(outputTimeFolder + "graphGenerationPDG.txt");
				File txtEDG = new File(outputTimeFolder + "graphGenerationCE-PDG.txt");

				if (!txtSDG.exists())
					txtSDG.createNewFile();
				if (!txtEDG.exists())
					txtEDG.createNewFile();

				FileWriter fw = new FileWriter(txtSDG, true);
				for (int i = 0; i < numberOfIterationsGen; i++) {
					fw.append(moduleName + ";" + standardTime[i] + "\n");
				}
				fw.close();

				FileWriter fw2 = new FileWriter(txtEDG, true);
				for (int i = 0; i < numberOfIterationsGen; i++) {
					fw2.append(moduleName + ";" + constrainedTime[i] + "\n");
				}
				fw2.close();
			} catch (IOException e) {
				System.out.println("An error occurred.");
				e.printStackTrace();
			}


			// INTRAPROCEDURAL GENERATION TIME
			// TIME MEASSUREMENT:
			// printCSVGenerationTime(a.file, standardTime, constrainedTime);

		}

		final LAST last = LASTFactory.createLAST(Language.Erlang, a.inputPath, true);
		final EDG edg = new EDGFactory(last).createEDG();
		/* ************************ */
		/* ** 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);

			// printHeadings("/Users/serperu/Desktop/SlicerOutput/Times/slicingStatistics.txt", a.file);
			int scCounter = 0;
			for (Node clause : clauses) {
				int arity = edg.getChildrenNonResult(edg.getChild(clause, Node.Type.Parameters)).size();
				String functionName = edg.getParent(clause).getName() + "/" + arity;

				List<Node> resultNodes = extractSlicingCriteria(edg, clause, a.file);

				// CONFIGURE MEASURED DIMENSIONS
				boolean measureSlicingTime = true;

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

				if (setName.equals("SetA"))
					scCounter = 0;

				for (Node SC : resultNodes) {
					// INITIALIZATIONS
					double[] standardTime = new double[numberOfIterationsSlice];
					double[] constrainedTime = new double[numberOfIterationsSlice];

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

							if (j == -1)
								continue;

							standardTime[j] = (finalStandardTime - initialStandardTime) / 1000.0;
						}

						for (int j = -1; j < numberOfIterationsSlice; j++) {
							long initialConstrainedTime = System.nanoTime();
							constrainedAlgorithm.slice(SC);
							long finalConstrainedTime = System.nanoTime();

							if (j == -1)
								continue;

							constrainedTime[j] = (finalConstrainedTime - initialConstrainedTime) / 1000.0;
						}

						printEachSCData(setName, moduleName, functionName, scCounter, standardTime, constrainedTime);
					}
					scCounter++;
				}
			}
		}
	}

	/** Extracts the possible SCs from a clause considering different factors commented inside the method body */
	public static List<Node> extractSlicingCriteria(EDG edg, Node clause, String fileName) {
		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: " + fileName);
//			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.");
			return new LinkedList<>();
		}

		/* FILTER SC NODES BY A CRITERION (CONSIDER ONLY VARIABLES) */
		resultNodes.removeIf(n -> edg.getNodeFromRes(n).getType() != Node.Type.Variable);
		/* REMOVE NODES GENERATED BY HIGH ORDER FUNS (e.g., fun g/2) */
		resultNodes.removeIf(n -> edg.getAncestor(n, Node.Type.AnonymousRoutine) != null &&
				edg.getNodeFromRes(n).getName().startsWith("FreshVar"));
		/* REMOVE DEAD CODE FROM BEING SLICING CRITERIA */
		resultNodes.removeIf(n -> edg.incomingEdgesOf(edg.getNodeFromRes(n)).stream().noneMatch(Edge::isControlFlowEdge));

		return resultNodes;
	}

	/** Generates the slice and store it for all possible slicing criteria */
	private static void sliceGenerationRun(Args a, String setName)
	{

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

		int scFunctionCounter = 0;
		/* ************************ */
		/* ** MEASUREMENT OF SCs ** */
		/* ************************ */
		// SC SELECTION
		List<Node> clauses = edg.getNodes(Node.Type.Clause);
		clauses.removeIf(c -> edg.getParent(c).getType() != Node.Type.Routine);

		for (Node clause : clauses) {
			Map<String,String> functionCriteria = new HashMap<>();
			List<Node> descendants = edg.getDescendants(clause);
			descendants.add(clause);

			List<Node> resultNodes = extractSlicingCriteria(edg,clause,a.file);

			int arity = edg.getChildrenNonResult(edg.getChild(clause, Node.Type.Parameters)).size();
			String functionName = edg.getParent(clause).getName() + "-" + arity;
			String moduleName = edg.getParent(edg.getParent(clause)).getName();
			moduleName = setName.equals("SetA") ? setName+"/"+moduleName + "-" + functionName : setName+"/"+moduleName;

			if (!resultNodes.isEmpty())
				new File(outputSliceGenerationFolder + moduleName).mkdirs();

			final SlicingAlgorithm standardAlgorithm = new AdaptedStandardAlgorithm(edg);
			final SlicingAlgorithm constrainedAlgorithm = new OnePassConstrainedAlgorithm(edg); // WITH LOOPS

			if(setName.equals("SetA"))
				scFunctionCounter = 0;

			for (Node SC : resultNodes) {
				Node normalNodeSC = edg.getNodeFromRes(SC);
				String scString = "<"+normalNodeSC.getInfo().getLine()+","+normalNodeSC.getName()+">";
				functionCriteria.put("#"+scFunctionCounter,scString);

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

				if (constrainedSlice.size() > standardSlice.size())
					throw new RuntimeException("The CE-PDG slice cannot be greater than the PDG slice");

				// PDG PRINT
				CodeFactory.createCode(Language.Erlang,
						new File(outputSliceGenerationFolder+moduleName+"/PDG"+"#"+scFunctionCounter+".erl"),
						edg, standardSlice);


				// CE-PDG PRINT
				CodeFactory.createCode(Language.Erlang,
						new File(outputSliceGenerationFolder+moduleName+"/CE-PDG"+"#"+scFunctionCounter+".erl"),
						edg, constrainedSlice);

				scFunctionCounter++;

			}
			if (scFunctionCounter > 0) {
				try {
					File txt = new File(outputSliceGenerationFolder + moduleName + "/criteria_map.txt");
					txt.createNewFile();
					FileWriter fw = new FileWriter(txt, true);
					for (String k : functionCriteria.keySet()) {
						fw.append(k + " => " + functionCriteria.get(k) + "\n");
					}
					fw.close();
				} catch (IOException e) {
					System.out.println("An error occurred.");
					e.printStackTrace();
				}
			}
		}
	}

	/** Method to count the number of SCs in each program or pair program-function */
	public static void SCCounter(Args a) {
		final LAST last = LASTFactory.createLAST(Language.Erlang, a.inputPath, true);
		final EDG edg = new EDGFactory(last).createEDG();

		// SC SELECTION
		List<Node> clauses = edg.getNodes(Node.Type.Clause);
		clauses.removeIf(c -> edg.getParent(c).getType() != Node.Type.Routine);
		int scFunctionCounter = 0;
		for (Node clause : clauses) {

			Map<String,String> functionCriteria = new HashMap<>();

			int arity = edg.getChildrenNonResult(edg.getChild(clause, Node.Type.Parameters)).size();
			String functionName = edg.getParent(clause).getName() + "-" + arity;
			String moduleName = edg.getParent(edg.getParent(clause)).getName();


			List<Node> descendants = edg.getDescendants(clause);
			descendants.add(clause);
			List<Node> resultNodes = extractSlicingCriteria(edg,clause,a.file);

			for (Node SC : resultNodes ){
				Node normalNodeSC = edg.getNodeFromRes(SC);
				String scString = "<"+normalNodeSC.getInfo().getLine()+","+normalNodeSC.getName()+">";
				functionCriteria.put("#"+scFunctionCounter,scString);
				scFunctionCounter++;
			}
//
//			Map<String,String> functionCriteriaIncomplete = new HashMap<>();
//			Map<String,String> InversefunctionCriteriaIncomplete = new HashMap<>();
//			List<Node> resultNodesIncomplete = extractSlicingCriteriaIncomplete(edg,clause,a.file);
//
//			for (Node SC : resultNodesIncomplete ){
//				Node normalNodeSC = edg.getNodeFromRes(SC);
//				String scString = "<"+normalNodeSC.getInfo().getLine()+","+normalNodeSC.getName()+">";
//				functionCriteriaIncomplete.put("#"+scFunctionCounterIncomplete,scString);
//				InversefunctionCriteriaIncomplete.put(scString,"#"+scFunctionCounterIncomplete);
//				scFunctionCounterIncomplete++;
//			}
//
//			Collection<String> okValues = functionCriteria.values();
//
//			for (String s : functionCriteriaIncomplete.values()) {
//				if (!okValues.contains(s)) {
//					System.out.println("Benchmark"+moduleName+"_"+functionName+"Remove SC "+InversefunctionCriteriaIncomplete.get(s)+" => "+s);
//				}
//			}

			try {
				new File(outputSliceGenerationFolder+"SlicingCriteriaMaps/"+moduleName+"/").mkdirs();
				File txt = new File(outputSliceGenerationFolder+"SlicingCriteriaMaps/"+moduleName+"/criteria.txt");
				txt.createNewFile();
				FileWriter fw = new FileWriter(txt,true);
				for(String k : functionCriteria.keySet()){
					fw.append(k +" => "+ functionCriteria.get(k)+"\n");
				}
				fw.close();
			} catch (IOException e) {
				System.out.println("An error occurred.");
				e.printStackTrace();
			}
		}
		System.out.println("\tBenchmark: "+ a.file + " => " + scFunctionCounter +" SCs");
	}

	/* *********************** *********************** *********************** *********************** */
	/* *********************** ****************** PRINT METHODS ************** *********************** */
	/* *********************** *********************** *********************** *********************** */
	public static void printEachSCData(String setName, String file, String funName, int iteration,double[] stdTime, double[] consTime) {

		new File(sliceTimeFolder + setName + "/").mkdirs();
		File outputFile = new File(sliceTimeFolder + setName + "/" + file + ".txt");

		FileWriter timeFileWriter;
		int numberOfElems = stdTime.length;
		try {
			if (!outputFile.exists())
				outputFile.createNewFile();

			timeFileWriter = new FileWriter(outputFile, true);

			// FILE; FunName; #SC; StandardTIME; ConstrainedTIME => ROW FORMAT
			for (int i = 0; i < numberOfElems; i++) {
				timeFileWriter.append(file + ";" + funName + ";" + "#"+ iteration + ";" + stdTime[i] + ";" + consTime[i] + "\n");
			}
			timeFileWriter.close();

		} catch (IOException e) {
			System.out.println("FILE NOT FOUND ERROR");
		}
	}

	/* *********************** *********************** *********************** *********************** */
	/* *********************** *********************** *********************** *********************** */
	/* *********************** *********************** *********************** *********************** */

	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();
		}
	}

	public 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; }
	}
}