src/main/java/org/apache/sysds/runtime/lineage/LineageDedupBlock.java

/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */

package org.apache.sysds.runtime.lineage;

import org.apache.sysds.runtime.DMLRuntimeException;
import org.apache.sysds.runtime.controlprogram.BasicProgramBlock;
import org.apache.sysds.runtime.controlprogram.IfProgramBlock;
import org.apache.sysds.runtime.controlprogram.ProgramBlock;
import org.apache.sysds.runtime.controlprogram.context.ExecutionContext;
import org.apache.sysds.runtime.instructions.Instruction;

import java.util.ArrayList;
import java.util.BitSet;
import java.util.Collection;
import java.util.HashMap;
import java.util.Map;
import java.util.Map.Entry;

public class LineageDedupBlock {
	private Map<Long, LineageMap> _distinctPaths = new HashMap<>();
	private BitSet _path = new BitSet();
	private int _numPaths = 0;
	
	private long _activePath = -1;
	private ArrayList<Long> _numDistinctPaths = new ArrayList<>();
	
	public LineageMap getActiveMap() {
		if (_activePath < 0 || !_distinctPaths.containsKey(_activePath))
			throw new DMLRuntimeException("Active path in LineageDedupBlock could not be found.");
		return _distinctPaths.get(_activePath);
	}
	
	public LineageMap getMap(Long path) {
		return _distinctPaths.containsKey(path) ? _distinctPaths.get(path) : null;
	}
	
	public void setMap(Long takenPath, LineageMap tracedMap) {
		_distinctPaths.put(takenPath, new LineageMap(tracedMap));
	}
	
	public boolean pathExists(Long path) {
		return _distinctPaths.containsKey(path);
	}
	
	public void resetPath() {
		_path.clear();
	}
	
	public void setPathBranch(int pos, boolean value) {
		_path.set(pos, value);
	}
	
	public long getPath() {
		return _path.length() == 0 ? 0 :
			_path.toLongArray()[0];
	}
	
	public boolean isAllPathsTaken() {
		return _distinctPaths.size() == _numDistinctPaths.size();
	}
	
	public void traceProgramBlocks(ArrayList<ProgramBlock> pbs, ExecutionContext ec) {
		if (_distinctPaths.size() == 0) //main path
			_distinctPaths.put(0L, new LineageMap());
		//process top-level blocks with changing set of all paths
		//Note: list copy required as distinct paths is modified
		for( ProgramBlock pb : pbs )
			traceProgramBlock(pb, ec, new ArrayList<>(_distinctPaths.entrySet()));
	}
	
	public void traceProgramBlock(ProgramBlock pb, ExecutionContext ec, Collection<Entry<Long, LineageMap>> paths) {
		if (pb instanceof IfProgramBlock)
			traceIfProgramBlock((IfProgramBlock) pb, ec, paths);
		else if (pb instanceof BasicProgramBlock)
			traceBasicProgramBlock((BasicProgramBlock) pb, ec, paths);
		else
			throw new DMLRuntimeException("Only BasicProgramBlocks or "
				+ "IfProgramBlocks are allowed inside a LineageDedupBlock.");
	}
	
	public void traceIfProgramBlock(IfProgramBlock ipb, ExecutionContext ec, Collection<Entry<Long, LineageMap>> paths) {
		//step 0: materialize branch position
		ipb.setLineageDedupPathPos(_numPaths++);
		
		//step 1: create new paths
		//replicate all existing paths in current scope for the new branch
		//(existing path IDs reflect the else branch)
		Map<Long, LineageMap> rep = new HashMap<>();
		int pathKey = 1 << (_numPaths-1);
		for (Map.Entry<Long, LineageMap> entry : paths) {
			Long pathIndex = entry.getKey() | pathKey;
			rep.put(pathIndex, new LineageMap(entry.getValue()));
		}
		_distinctPaths.putAll(rep);
		
		//step 3: trace if and else branches separately
		for (ProgramBlock pb : ipb.getChildBlocksIfBody())
			traceProgramBlock(pb, ec, rep.entrySet());
		for (ProgramBlock pb : ipb.getChildBlocksElseBody())
			traceProgramBlock(pb, ec, paths);
	}
	
	public void traceBasicProgramBlock(BasicProgramBlock bpb, ExecutionContext ec, Collection<Entry<Long,LineageMap>> paths) {
		for (Entry<Long, LineageMap> entry : paths) {
			_activePath = entry.getKey();
			for (Instruction inst : bpb.getInstructions())
				entry.getValue().trace(inst, ec);
		}
	}
	// compute and save the number of distinct paths
	public void setNumPathsInPBs (ArrayList<ProgramBlock> pbs, ExecutionContext ec) {
		if (_numDistinctPaths.size() == 0) 
			_numDistinctPaths.add(0L);
		for (ProgramBlock pb : pbs)
			numPathsInPB(pb, ec, _numDistinctPaths);
	}
	
	private void numPathsInPB(ProgramBlock pb, ExecutionContext ec, ArrayList<Long> paths) {
		if (pb instanceof IfProgramBlock)
			numPathsInIfPB((IfProgramBlock)pb, ec, paths);
		else if (pb instanceof BasicProgramBlock)
			return;
		else
			throw new DMLRuntimeException("Only BasicProgramBlocks or "
				+ "IfProgramBlocks are allowed inside a LineageDedupBlock.");
	}
	
	private void numPathsInIfPB(IfProgramBlock ipb, ExecutionContext ec, ArrayList<Long> paths) {
		ipb.setLineageDedupPathPos(_numPaths++);
		ArrayList<Long> rep = new ArrayList<>();
		int pathKey = 1 << (_numPaths-1);
		for (long p : paths) {
			long pathIndex = p | pathKey;
			rep.add(pathIndex);
		}
		_numDistinctPaths.addAll(rep);
		for (ProgramBlock pb : ipb.getChildBlocksIfBody())
			numPathsInPB(pb, ec, rep);
		for (ProgramBlock pb : ipb.getChildBlocksElseBody())
			numPathsInPB(pb, ec, paths);
	}
}