eclipse-tools/responseTime-analyzer/plugins/org.eclipse.app4mc.gsoc_rta/src/org/eclipse/app4mc/gsoc_rta/RuntimeUtilRTA.java

/*******************************************************************************
 * Copyright (c) 2019 Dortmund University of Applied Sciences and Arts.
 *
 * This program and the accompanying materials
 * are made available under the terms of the Eclipse Public License 2.0
 * which accompanies this distribution, and is available at
 * https://www.eclipse.org/legal/epl-2.0/
 *
 * SPDX-License-Identifier: EPL-2.0
 *
 * Contributors: FH Dortmund - initial API and implementation
 * 
 *******************************************************************************/
package org.eclipse.app4mc.gsoc_rta;

import java.math.BigInteger;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;

import org.apache.log4j.Logger;
import org.eclipse.app4mc.amalthea.model.AmaltheaServices;
import org.eclipse.app4mc.amalthea.model.CallSequenceItem;
import org.eclipse.app4mc.amalthea.model.ClearEvent;
import org.eclipse.app4mc.amalthea.model.InterProcessStimulus;
import org.eclipse.app4mc.amalthea.model.InterProcessTrigger;
import org.eclipse.app4mc.amalthea.model.Label;
import org.eclipse.app4mc.amalthea.model.LabelAccess;
import org.eclipse.app4mc.amalthea.model.LabelAccessEnum;
import org.eclipse.app4mc.amalthea.model.ProcessingUnit;
import org.eclipse.app4mc.amalthea.model.Runnable;
import org.eclipse.app4mc.amalthea.model.SetEvent;
import org.eclipse.app4mc.amalthea.model.Task;
import org.eclipse.app4mc.amalthea.model.TaskRunnableCall;
import org.eclipse.app4mc.amalthea.model.Ticks;
import org.eclipse.app4mc.amalthea.model.Time;
import org.eclipse.app4mc.amalthea.model.TimeUnit;
import org.eclipse.app4mc.amalthea.model.WaitEvent;
import org.eclipse.app4mc.amalthea.model.util.FactoryUtil;
import org.eclipse.app4mc.amalthea.model.util.RuntimeUtil;
import org.eclipse.app4mc.amalthea.model.util.RuntimeUtil.TimeType;
import org.eclipse.app4mc.amalthea.model.util.SoftwareUtil;
import org.eclipse.emf.common.util.EList;

/**
 * Date: June 21-2019 
 * @author Junhyung Ki
 * @version 1.0
 *					This class is to support CpuRTA class. Response Time Analysis contains low level calculation 
 *					such as deriving execution time of a Task or Runnable. Execution time calculation varies depending on the analyzed model. 
 *					Therefore, it is necessary to separate from Response Time calculation to increase adaptability.
 *					Only 'getExecutionTimeforCPUTask' method is accessible for CpuRTA and the rest are sub-methods of it.
 */
public class RuntimeUtilRTA {
	/**
	 * Calculate execution time of the given task under one of the several configurations.
	 * Since this method is used by CPURtaIA, the visibility should be 'protected'
	 * 1. triggering task in the synchronous mode
	 * 2. triggering task in the asynchronous mode
	 * 3. GPU task on CPU
	 * 4. task with only Ticks
	 * 
	 * @param task				the observed task
	 * @param pu				ProcessingUnit that would compute the given task (A57 or Denver)
	 * @param executionCase		BCET, ACET, WCET
	 * @param trt				HashMap that would contain the corresponding GPU task's response time
	 * @param cpurta			the instance of CPURtaIA class that calls this method
	 * 							(to access to the cumuAcTime Time variable that accumulate access latency)
	 * @return
	 * 			execution time of the observed task
	 */
	protected Time getExecutionTimeforCPUTask(final Task task, final ProcessingUnit pu, final TimeType executionCase, final CpuRTA cpurta) {
		Logger.getLogger(RuntimeUtilRTA.class);
		// TODO: Contention Parameter
		/* set the default result time variable as 0s */
		Time result = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
		/* check if the current task is a triggering task.
		 * If so, check whether or not it triggers the target task which is newly mapped to CPU.
		 * In that case, returns 0 ps */
		if (doesThisTaskTriggerCPUTask(task, cpurta)) {
			return result;
		}
		// TODO: Contention
		/* The list of runnables of the given task */
		final List<Runnable> runnableList = SoftwareUtil.getRunnableList(task, null);
		/* To identify the index of the triggerEvent */
		final List<CallSequenceItem> callSequenceList = SoftwareUtil.collectCalls(task, null, 
				(call -> call instanceof TaskRunnableCall || call instanceof InterProcessTrigger || call instanceof ClearEvent
						|| call instanceof SetEvent || call instanceof WaitEvent));
		int indexforTrigger = 0;
		for (int i = 0; i < callSequenceList.size(); i++) {
			if (callSequenceList.get(i) instanceof InterProcessTrigger) {
				indexforTrigger = i;
			}
		}
		/* To distinguish CPU Tasks between Sync & Async */
		if (isTriggeringTask(task)) {
			/* all should be synchronous (wait should not be ignored) - active wait */
			if (SharedConsts.synchronousOffloading == true) {
				result = syncTypeOperation(indexforTrigger, callSequenceList, runnableList, pu, executionCase, cpurta);
				/* if this task has the OffloadingAsync runnable, subtract the runnable part from the result */
				if (doesTaskHaveAsyncRunnable(task, cpurta)) {
					result = result.subtract(getExecutionTimeForRTARunnable(cpurta.offloadingAsyncRunnable, pu, executionCase));
				}
			}
			/* all should be asynchronous (wait should be ignored) - passive wait */
			else {
				result = asyncTypeOperation(runnableList, pu, executionCase);
				/* if this task is missing the OffloadingAsync runnable, add the runnable part to the result */
				if (!doesTaskHaveAsyncRunnable(task, cpurta)) {
					result = result.add(getExecutionTimeForRTARunnable(cpurta.offloadingAsyncRunnable, pu, executionCase));
				}
			}
		}
		else {
			/* GPU Origin Task on CPU & No Triggering Behavior (No InterProcessTrigger) */
			if (!(callSequenceList.get(indexforTrigger) instanceof InterProcessTrigger)) {
				/* GPU Origin task that is newly mapped to CPU */
				if (cpurta.getGpuTaskList().contains(task)) {
					result = result.add(getExecutionTimeForGPUTaskOnCPU(task, runnableList, pu, executionCase, cpurta));
					// TODO: result = result.add(contention);
					return result;
				}
				/* No Triggering Behavior (No InterProcessTrigger) */
				for (final Runnable r : runnableList) {
					result = result.add(getExecutionTimeForRTARunnable(r, pu, executionCase));
				}
				// TODO: result = result.add(contention);
				return result;
			}
		}
		// TODO: result = result.add(contention);
		return result;
	}

	/**
	 * Find out whether the given triggering task(that has an InterProcessTrigger) triggers a GPU task which is newly mapped to CPU.
	 * If the ProcessingUnit index of the triggered task is bigger than the biggest CPU index, that means the triggered task is mapped to GPU
	 * which would return false.
	 * 
	 * @param task			the observed task
	 * @param cpurta		the instance of CPURtaIA class that calls this method
	 * 						(to get the task List & the integer array to identify the ProcessingUnit index of the triggered task)
	 * @return
	 * 			boolean value (true: the observed task triggers a task that is mapped to CPU / 
	 * 						   false: the observed task triggers a task that is mapped to GPU)
	 */
	private boolean doesThisTaskTriggerCPUTask(final Task task, final CpuRTA cpurta) {
		if (cpurta.getTriggeringTaskList().contains(task)) {
			final List<CallSequenceItem> callList = SoftwareUtil.collectCalls(task, null, 
					(call -> call instanceof TaskRunnableCall || call instanceof InterProcessTrigger || call instanceof ClearEvent
							|| call instanceof SetEvent || call instanceof WaitEvent));
			final InterProcessStimulus ips = ((InterProcessTrigger) callList.stream().filter(s -> s instanceof InterProcessTrigger).iterator().next())
					.getStimulus();
			final EList<Task> allTaskList = cpurta.getModel().getSwModel().getTasks();
			final int[] ia = cpurta.getIA();
			final int cpuThreshold = CommonUtils.getNumberofCPUs(cpurta.getModel()) - 1;
			for (int i = 0; i < ia.length; i++) {
				if (ia[i] > cpuThreshold) {
					final Task theTask = allTaskList.get(i);
					if (theTask.getStimuli().get(0) instanceof InterProcessStimulus) {
						final InterProcessStimulus thisIPS = (InterProcessStimulus) theTask.getStimuli().get(0);
						if (ips.equals(thisIPS)) {
							Logger.getLogger(RuntimeUtilRTA.class).debug("Confirmation: The triggered task mapped to (GPU)");
							return false;
						}
					}
				}
			}
			Logger.getLogger(RuntimeUtilRTA.class).debug("Confirmation: The triggered task mapped to (CPU)");
			return true;
		}
		return false;
	}

	/**
	 * Calculate execution time of the given runnableList in a synchronous manner.
	 * (execution time of pre-processing) + GPU task response time + (execution time of post-processing)
	 * 
	 * @param indexforTrigger	Integer variable that is used to get InterProcessTrigger to identify the triggered GPU task
	 * @param callSequenceList	callSequenceList List variable that is used to get InterProcessTrigger to identify the triggered GPU task
	 * @param runnableList		the observed runnable List to calculate execution time in the synchronous mode
	 * @param trt				HashMap that would contain the corresponding GPU task's response time
	 * @param pu				ProcessingUnit that would compute the given runnable (A57 or Denver)
	 * @param executionCase		BCET, ACET, WCET
	 * @param cpurta			the instance of CPURtaIA class that calls this method
	 * 							(to get the identified triggered GPU task in the model)
	 * 							(to access to the cumuAcTime Time variable that accumulate access latency)
	 * @return
	 * 			synchronous execution time of the observed set
	 */
	private Time syncTypeOperation(final int indexforTrigger, final List<CallSequenceItem> callSequenceList, final List<Runnable> runnableList,
			final ProcessingUnit pu, final TimeType executionCase, final CpuRTA cpurta) {
		Logger.getLogger(RuntimeUtilRTA.class).debug("TYPE: SYNC");
		/* set the default result time variable as 0s */
		Time result = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
		/* Sum all the runnable ExecutionTime of the CPU Task */
		for (final Runnable r : runnableList) {
			result = result.add(getExecutionTimeForRTARunnable(r, pu, executionCase));
		}
		final InterProcessTrigger ipt = (InterProcessTrigger) callSequenceList.get(indexforTrigger);
		final Task triggeredGPUTask = cpurta.getModel().getSwModel().getTasks().stream().filter(t -> t.getStimuli().get(0).equals(ipt.getStimulus())).iterator()
				.next();
		result = result.add(cpurta.getTRT().get(triggeredGPUTask));
		return result;
	}

	/**
	 * Calculate execution time of the given runnableList in an asynchronous manner.
	 * (execution time of pre-processing) + (execution time of post-processing) 
	 * 
	 * @param runnableList		the observed runnable List to calculate execution time in the asynchronous mode
	 * @param pu				ProcessingUnit that would compute the given runnable (A57 or Denver)
	 * @param executionCase		BCET, ACET, WCET
	 * @return
	 * 			asynchronous execution time of the observed runnable List
	 */
	private Time asyncTypeOperation(final List<Runnable> runnableList, final ProcessingUnit pu, final TimeType executionCase) {
		Logger.getLogger(RuntimeUtilRTA.class).debug("TYPE: ASYNC");
		/**
		 * <Asynchronous Task> et_t=sum_{runnable calls before GPU trigger
		 * event}et_r + et_{runnable calls after GPU trigger event};
		 */
		/* set the default result time variable as 0s */
		Time result = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
		/* Sum all the runnable ExecutionTime */
		for (final Runnable r : runnableList) {
			/* In case of Pre_Detection_Post task, the AsyncOffloading runnable is already taken into account here. */
			result = result.add(getExecutionTimeForRTARunnable(r, pu, executionCase));
		}
		return result;
	}

	/**
	 * Identify whether or not the given task has the OffloadingAsyncCosts Runnable (that takes costs into account in the Asynchronous mode)
	 * which some triggering tasks do not have.
	 * Since this method is used by CPURtaIA, the visibility should be 'protected'
	 * 
	 * @param task			the observed task
	 * @param cpurta		the instance of CPURtaIA class that calls this method
	 * 						(to access to the triggeringTaskList List<Task> variable that contains tasks with an InterProcessTrigger)
	 * @return
	 * 			boolean value of the result
	 */
	protected static boolean doesTaskHaveAsyncRunnable (final Task task, final CpuRTA cpurta) {
		boolean result = false;
		if (cpurta.getTriggeringTaskList().contains(task)) {
			final List<CallSequenceItem> callList = SoftwareUtil.collectCalls(task, null, 
					(call -> call instanceof TaskRunnableCall || call instanceof InterProcessTrigger || call instanceof ClearEvent
							|| call instanceof SetEvent || call instanceof WaitEvent));
			final int waitIndex = callList.indexOf(callList.stream().filter(s -> s instanceof WaitEvent).iterator().next());
			final int clearIndex = callList.indexOf(callList.stream().filter(s -> s instanceof ClearEvent).iterator().next());
			if ((clearIndex - waitIndex) > 1) {
				result = true;
			}
		}
		else {
			Logger.getLogger(RuntimeUtilRTA.class).debug("ERROR: This task is not a triggering task!!");
		}
		return result;
	}
	
	/**
	 * Calculate execution time of the given task which was originally designed for GPU but newly mapped to CPU by Generic Algorithm Mapping.
	 * It should ignore offloading runnables and take the required labels(read from pre-processing, write from post-processing) into account.
	 * The method follows Read / Compute(Ticks) / Write semantic.
	 * Read(Write)_Access_Time = Round_UP(Size_of_Read_Labels / 64.0 Bytes) * (Read_Latency / Frequency)
	 * 
	 * @param task				the observed task
	 * @param runnableList		runnable list of the given task
	 * @param pu				ProcessingUnit that would compute the given runnable (A57 or Denver)
	 * @param executionCase		BCET, ACET, WCET
	 * @param cpurta			the instance of CPURtaIA class that calls this method
	 * 							(to access to the gpuToCpuLabels HashMap variable that contains List<Label> of required read & write labels)
	 * @return
	 * 			execution time of the observed task
	 */
	private Time getExecutionTimeForGPUTaskOnCPU(final Task task, final List<Runnable> runnableList, final ProcessingUnit pu, 
			final TimeType executionCase, final CpuRTA cpurta) {
		Logger.getLogger(RuntimeUtilRTA.class).debug("TYPE: GPUTaskOnCPU // " + "Task: " + task.getName());
		Time result = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
		Runnable funcRunnable = null;
		for (final Runnable r : runnableList) {
			final List<Ticks> thisTicksList = SoftwareUtil.getTicks(r, null);
			if (thisTicksList.size() != 0) {
				funcRunnable = r;
				break;
			}
		}
		final Time parameter = FactoryUtil.createTime(BigInteger.ONE, TimeUnit.S);
		final double freq = AmaltheaServices.convertToHertz(pu.getFrequencyDomain().getDefaultValue()).longValue();
		final HashMap<Task, List<Label>[]> gtcl = cpurta.getGTCL();
		final List<Label>[] thisLabelList = gtcl.get(task);
		final List<Label> readLabelList = thisLabelList[0];
		final List<Label> writeLabelList = thisLabelList[1];
		for (final Label l : readLabelList) {
			Logger.getLogger(RuntimeUtilRTA.class).debug("Label(Read): " + l.getName() + " // (" + task.getName() + ")");
		}
		for (final Label l : writeLabelList) {
			Logger.getLogger(RuntimeUtilRTA.class).debug("Label(Write): " + l.getName() + " // (" + task.getName() + ")");
		}
		double readLatency = 0;
		double writeLatency = 0;
		if (executionCase.equals(TimeType.WCET)) {
			readLatency = pu.getAccessElements().get(0).getReadLatency().getUpperBound();
			writeLatency = pu.getAccessElements().get(0).getWriteLatency().getUpperBound();
		}
		else if (executionCase.equals(TimeType.BCET)) {
			readLatency = pu.getAccessElements().get(0).getReadLatency().getLowerBound();
			writeLatency = pu.getAccessElements().get(0).getWriteLatency().getLowerBound();
		}
		else {
			readLatency = pu.getAccessElements().get(0).getReadLatency().getAverage();
			writeLatency = pu.getAccessElements().get(0).getWriteLatency().getAverage();
		}
		/* Read (LabelAccess): */
		double readAccessParameter = 0;
		double sizeofReadLabels = 0;
		for (final Label rl : readLabelList) {
			sizeofReadLabels += rl.getSize().getNumberBytes();
		}
		readAccessParameter = (Math.ceil(sizeofReadLabels / 64.0) * (readLatency / freq));
		final Time readAccess = parameter.multiply(readAccessParameter);
		result = result.add(readAccess); // LabelAccess(Read) added
		/* Execution (Ticks): */
		final List<Ticks> ticksList = SoftwareUtil.getTicks(funcRunnable, null);
		for (final Ticks t : ticksList) {
			final Time tickExecution = RuntimeUtil.getExecutionTimeForTicks(t, pu, executionCase);
			result = result.add(tickExecution); // Execution(Ticks) added
		}
		/* Write (LabelAccess): */
		double writeAccessParameter = 0;
		double sizeofWriteLabels = 0;
		for (final Label wl : writeLabelList) {
			sizeofWriteLabels += wl.getSize().getNumberBytes();
		}
		writeAccessParameter = (Math.ceil(sizeofWriteLabels / 64.0) * (writeLatency / freq));
		final Time writeAccess = parameter.multiply(writeAccessParameter);
		result = result.add(writeAccess); // LabelAccess(Write) added
		return result;
	}
	
	/**
	 * Calculate execution time of the given runnable.
	 * The method consider Read / Compute(Ticks) / Write semantic.
	 * 
	 * @param runnable			the observed runnable
	 * @param pu				ProcessingUnit that would compute the given runnable (A57 or Denver)
	 * @param executionCase		BCET, ACET, WCET
	 * @return
	 * 			execution time of the observed runnable
	 */
	protected Time getExecutionTimeForRTARunnable(final Runnable runnable, final ProcessingUnit pu, final TimeType executionCase) {
		Logger.getLogger(RuntimeUtilRTA.class).debug(executionCase.toString());
		Time result = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
		final double freq = AmaltheaServices.convertToHertz(pu.getFrequencyDomain().getDefaultValue()).longValue();
		double readLatency = 0;
		double writeLatency = 0;
		if (executionCase.equals(TimeType.WCET)) {
			readLatency = pu.getAccessElements().get(0).getReadLatency().getUpperBound();
			writeLatency = pu.getAccessElements().get(0).getWriteLatency().getUpperBound();
		}
		else if (executionCase.equals(TimeType.BCET)) {
			readLatency = pu.getAccessElements().get(0).getReadLatency().getLowerBound();
			writeLatency = pu.getAccessElements().get(0).getWriteLatency().getLowerBound();
		}
		else {
			readLatency = pu.getAccessElements().get(0).getReadLatency().getAverage();
			writeLatency = pu.getAccessElements().get(0).getWriteLatency().getAverage();
		}
		/* Read & Write Memory Access Time */
		result = result.add(getRunnableMemoryAccessTime(runnable, freq, readLatency, writeLatency));
		
		/* Execution (Ticks): */
		final List<Ticks> ticksList = SoftwareUtil.getTicks(runnable, null);
		for (final Ticks t : ticksList) {
			final Time tickExecution = RuntimeUtil.getExecutionTimeForTicks(t, pu, executionCase);
			result = result.add(tickExecution); // Execution(Ticks) added
		}
		return result;
	}

	/**
	 * Calculate memory access time of the observed task.
	 * Since this method is used by CPURtaIA, the visibility should be 'protected'
	 * 
	 * @param task				the observed task
	 * @param pu				ProcessingUnit that would compute the given runnable (A57 or Denver)
	 * @param executionCase		BCET, ACET, WCET
	 * @return
	 * 			memory access time of the observed task
	 */
	protected Time getTaskMemoryAccessTime (final Task task, final ProcessingUnit pu, final TimeType executionCase) {
		Time result = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
		final double freq = AmaltheaServices.convertToHertz(pu.getFrequencyDomain().getDefaultValue()).longValue();
		final List<Runnable> runnableList = SoftwareUtil.getRunnableList(task, null);
		double readLatency = 0;
		double writeLatency = 0;
		if (executionCase.equals(TimeType.WCET)) {
			readLatency = pu.getAccessElements().get(0).getReadLatency().getUpperBound();
			writeLatency = pu.getAccessElements().get(0).getWriteLatency().getUpperBound();
		}
		else if (executionCase.equals(TimeType.BCET)) {
			readLatency = pu.getAccessElements().get(0).getReadLatency().getLowerBound();
			writeLatency = pu.getAccessElements().get(0).getWriteLatency().getLowerBound();
		}
		else {
			readLatency = pu.getAccessElements().get(0).getReadLatency().getAverage();
			writeLatency = pu.getAccessElements().get(0).getWriteLatency().getAverage();
		}
		for(final Runnable r : runnableList ) {
			result = result.add(getRunnableMemoryAccessTime(r, freq, readLatency, writeLatency));
		}
		return result;
	}
	
	/**
	 * Calculate memory access time of the observed runnable.
	 * The method follows Read / Compute(Ticks) / Write semantic.
	 * Read(Write)_Access_Time = Round_UP(Size_of_Read_Labels / 64.0 Bytes) * (Read_Latency / Frequency)
	 * 
	 * @param runnable			the observed runnable
	 * @param frequency			frequency value of the Processing Unit
	 * @param readLatency		readLatency value of the Processing Unit
	 * @param writeLatency		writeLatency value of the Processing Unit
	 * @return
	 * 			memory access time of the observed runnable
	 */
	private Time getRunnableMemoryAccessTime (final Runnable runnable, final double frequency, 
			final double readLatency, final double writeLatency) {
		Time result = FactoryUtil.createTime(BigInteger.ZERO, TimeUnit.PS);
		final Time parameter = FactoryUtil.createTime(BigInteger.ONE, TimeUnit.S);
		final List<LabelAccess> thisLAList = SoftwareUtil.getLabelAccessList(runnable, null);
		final List<LabelAccess> readList = thisLAList.stream().filter(x -> (x.getAccess()).equals(LabelAccessEnum.READ)).collect(Collectors.toList());
		final List<LabelAccess> writeList = thisLAList.stream().filter(x -> (x.getAccess()).equals(LabelAccessEnum.WRITE)).collect(Collectors.toList());
		/* Read (LabelAccess): */
		double readAccessParameter = 0;
		double sizeofReadLabels = 0;
		for (final LabelAccess rl : readList) {
			sizeofReadLabels += rl.getData().getSize().getNumberBytes();
		}
		readAccessParameter = (Math.ceil(sizeofReadLabels / 64.0) * (readLatency / frequency));
		final Time readAccess = parameter.multiply(readAccessParameter);
		result = result.add(readAccess); // LabelAccess(Read) added
		
		/* Write (LabelAccess): */
		double writeAccessParameter = 0;
		double sizeofWriteLabels = 0;
		for (final LabelAccess wl : writeList) {
			sizeofWriteLabels += wl.getData().getSize().getNumberBytes();
		}
		writeAccessParameter = (Math.ceil(sizeofWriteLabels / 64.0) * (writeLatency / frequency));
		final Time writeAccess = parameter.multiply(writeAccessParameter);
		result = result.add(writeAccess); // LabelAccess(Write) added
		return result;
	}

	/**
	 * Identify whether the given task has an InterProcessTrigger or not.
	 * 
	 * @param task			the observed task
	 * @return
	 * 			boolean value of the result
	 */
	protected static boolean isTriggeringTask(final Task task) {
		/* true: Triggering Task, false: Non-Triggering Task */
		boolean result = false;
		final List<CallSequenceItem> callList = SoftwareUtil.collectCalls(task, null, 
				(call -> call instanceof TaskRunnableCall || call instanceof InterProcessTrigger || call instanceof ClearEvent
						|| call instanceof SetEvent || call instanceof WaitEvent));
		List<CallSequenceItem> iptList = callList.stream().filter(s -> s instanceof InterProcessTrigger).collect(Collectors.toList());
		if (iptList.size() != 0) {
			result = true;
		}
		return result;
	}
}