content: /*******************************************************************************
   * Copyright (c) 2009, 2019 Mountainminds GmbH & Co. KG and Contributors
   * All rights reserved. This program and the accompanying materials
   * are made available under the terms of the Eclipse Public License v1.0
   * which accompanies this distribution, and is available at
   * http://www.eclipse.org/legal/epl-v10.html
   *
   * Contributors:
   *    Evgeny Mandrikov - initial API and implementation
   *
   *******************************************************************************/
  package org.jacoco.core.internal.analysis.filter;
  
  import java.util.HashSet;
  import java.util.List;
  import java.util.Set;
  
  import org.objectweb.asm.Opcodes;
  import org.objectweb.asm.tree.AbstractInsnNode;
  import org.objectweb.asm.tree.JumpInsnNode;
  import org.objectweb.asm.tree.MethodNode;
  import org.objectweb.asm.tree.TryCatchBlockNode;
  import org.objectweb.asm.tree.VarInsnNode;
  
  /**
   * Filters duplicates of finally blocks that compiler generates.
   *
   * To understand algorithm of filtering, consider following example:
   * 
   * <pre>
   * try {
   * 	if (x) {
   * 		a();
   * 		return; // 1
   * 	}
   * 	b(); // 2
   * } catch (Exception e) {
   * 	c(); // 3
   * } finally {
   * 	d(); // 4
   * }
   * </pre>
   *
   * There are 4 <b>distinct</b> points of exit out of these "try/catch/finally"
   * blocks - three without exception, and one with Throwable if it is thrown
   * prior to reaching first three points of exit.
   * 
   * "finally" block must be executed just before these points, so there must be 4
   * copies of its bytecode instructions.
   *
   * One of them handles Throwable ("catch-any") and must cover all instructions
   * of "try/catch" blocks. But must not cover instructions of other duplicates,
   * because instructions of "finally" block also can cause Throwable to be
   * thrown.
   *
   * Therefore there will be multiple {@link MethodNode#tryCatchBlocks} with
   * {@link TryCatchBlockNode#type} null with same
   * {@link TryCatchBlockNode#handler} for different non-intersecting bytecode
   * regions ({@link TryCatchBlockNode#start}, {@link TryCatchBlockNode#end}).
   *
   * And each exit out of these regions, except one that handles Throwable, will
   * contain duplicate of "finally" block.
   *
   * To determine exits out of these regions, they all must be processed together
   * at once, because execution can branch from one region to another (like it is
   * in given example due to "if" statement).
   */
  public final class FinallyFilter implements IFilter {
  
  	public void filter(final MethodNode methodNode,
  			final IFilterContext context, final IFilterOutput output) {
  		for (final TryCatchBlockNode tryCatchBlock : methodNode.tryCatchBlocks) {
  			if (tryCatchBlock.type == null) {
  				filter(output, methodNode.tryCatchBlocks, tryCatchBlock);
  			}
  		}
  	}
  
  	private static void filter(final IFilterOutput output,
  			final List<TryCatchBlockNode> tryCatchBlocks,
  			final TryCatchBlockNode catchAnyBlock) {
  		final AbstractInsnNode e = next(catchAnyBlock.handler);
  		final int size = size(e);
  		if (size <= 0) {
  			return;
  		}
  
  		// Determine instructions inside regions
  		final Set<AbstractInsnNode> inside = new HashSet<AbstractInsnNode>();
  		for (final TryCatchBlockNode t : tryCatchBlocks) {
  			if (t.handler == catchAnyBlock.handler) {
  				AbstractInsnNode i = t.start;
  				while (i != t.end) {
  					inside.add(i);
  					i = i.getNext();
  				}
  			}
  		}
  
  		// Find and merge duplicates at exits of regions
  		for (final TryCatchBlockNode t : tryCatchBlocks) {
  			if (t.handler == catchAnyBlock.handler) {
  				boolean continues = false;
  				AbstractInsnNode i = t.start;
  
  				while (i != t.end) {
  					switch (i.getType()) {
  					case AbstractInsnNode.FRAME:
  					case AbstractInsnNode.LINE:
  					case AbstractInsnNode.LABEL:
  						break;
  					case AbstractInsnNode.JUMP_INSN:
  						final AbstractInsnNode jumpTarget = next(
  								((JumpInsnNode) i).label);
  						if (!inside.contains(jumpTarget)) {
  							merge(output, size, e, jumpTarget);
  						}
  						continues = i.getOpcode() != Opcodes.GOTO;
  						break;
  					default:
  						switch (i.getOpcode()) {
  						case Opcodes.IRETURN:
  						case Opcodes.LRETURN:
  						case Opcodes.FRETURN:
  						case Opcodes.DRETURN:
  						case Opcodes.ARETURN:
  						case Opcodes.RETURN:
  						case Opcodes.ATHROW:
  							continues = false;
  							break;
  						default:
  							continues = true;
  							break;
  						}
  						break;
  					}
  					i = i.getNext();
  				}
  
  				i = next(i);
  				if (continues && !inside.contains(i)) {
  					merge(output, size, e, i);
  				}
  			}
  
  			if (t != catchAnyBlock && t.start == catchAnyBlock.start
  					&& t.end == catchAnyBlock.end) {
  				final AbstractInsnNode i = next(next(t.handler));
  				if (!inside.contains(i)) {
  					// javac's empty catch - merge after ASTORE
  					merge(output, size, e, i);
  				}
  			}
  		}
  	}
  
  	private static void merge(final IFilterOutput output, final int size,
  			AbstractInsnNode e, AbstractInsnNode n) {
  		if (!isSame(size, e, n)) {
  			return;
  		}
  		output.ignore(e, e);
  		e = next(e);
  		for (int i = 0; i < size; i++) {
  			output.merge(e, n);
  			e = next(e);
  			n = next(n);
  		}
  		output.ignore(e, next(e));
  
  		if (n != null && n.getOpcode() == Opcodes.GOTO) {
  			// goto instructions at the end of non-executed duplicates
  			// cause partial coverage of last line of finally block,
  			// so should be ignored
  			output.ignore(n, n);
  		}
  	}
  
  	private static boolean isSame(final int size, AbstractInsnNode e,
  			AbstractInsnNode n) {
  		e = next(e);
  		for (int i = 0; i < size; i++) {
  			if (n == null || e.getOpcode() != n.getOpcode()) {
  				return false;
  			}
  			e = next(e);
  			n = next(n);
  		}
  		return true;
  	}
  
  	/**
  	 * @return number of instructions inside given "catch-any" handler
  	 */
  	private static int size(AbstractInsnNode i) {
  		if (Opcodes.ASTORE != i.getOpcode()) {
  			// when always completes abruptly
  			return 0;
  		}
  		final int var = ((VarInsnNode) i).var;
  		int size = -1;
  		do {
  			size++;
  			i = next(i);
  			if (i == null) {
  				// when always completes abruptly
  				return 0;
  			}
  		} while (!(Opcodes.ALOAD == i.getOpcode()
  				&& var == ((VarInsnNode) i).var));
  		i = next(i);
  		if (Opcodes.ATHROW != i.getOpcode()) {
  			return 0;
  		}
  		return size;
  	}
  
  	private static AbstractInsnNode next(AbstractInsnNode i) {
  		do {
  			i = i.getNext();
  		} while (i != null && (AbstractInsnNode.FRAME == i.getType()
  				|| AbstractInsnNode.LABEL == i.getType()
  				|| AbstractInsnNode.LINE == i.getType()));
  		return i;
  	}
  
  }
  